📄 readme.html

📁 parser in C++~~~~~~~~~~~~
💻 HTML
📖 第 1 页 / 共 3 页
字号:
12 3 下一页
<?xml version="1.0" encoding="UTF-8"?><!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"      "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head>  <meta http-equiv="content-type" content="text/html; charset=UTF-8" />  <title>COMP151 Programming Assignment 1, Spring 2007</title></head><body><h1>COMP151 Programming Assignment 1, Spring 2007</h1><p><strong>Author:</strong> <a href="http://www.cs.ust.hk/~dekai/">DekaiWu</a></p><p><strong>Date:</strong> Due 2007.03.08 at 23:00 by CASS</p><p><strong>Download:</strong> <ahref="http://www.cs.ust.hk/~dekai/151/assignments/a1.tar.gz">http://www.cs.ust.hk/~dekai/151/assignments/a1.tar.gz</a></p><p><strong>Assignment page:</strong> <ahref="http://www.cs.ust.hk/~dekai/151/assignments/a1/html/">http://www.cs.ust.hk/~dekai/151/assignments/a1/html/</a></p><p><strong>Course page:</strong> <ahref="http://www.cs.ust.hk/~dekai/151/">http://www.cs.ust.hk/~dekai/151/</a></p><h3>Your assignment</h3><p>You've been assigned to write an <em>expression evaluator</em>. The inputexpressions to your evaluator will be strings in a traditional computerscience notation known as <ahref="http://en.wikipedia.org/wiki/S-expression"><em>s-expressions</em></a>,which is a prefix notation that is fully parenthesized to avoid ambiguity,for example:</p><p><tt>(+ 2 3 4 5)</tt><br /><tt>(+ 2 3.5)</tt><br /><tt>(+ 2)</tt><br /><tt>(+)</tt><br /><tt>(+ (+ -2 5 -1) 3.5)</tt><br /><tt>(ceiling 4.7)</tt><br /><tt>(ceiling 4.0)</tt><br /><tt>(ceiling -4.7)</tt><br /><tt>(if 5 7 8.3)</tt><br /><tt>(if 0 7 8.3)</tt><br /><tt>(if (+ 2 3) (ceiling 6.1) (+ 4 2.3 2))</tt><br /><tt>(if (+ 2 -2) (ceiling 6.1) (+ 4 2.3 2))</tt><br /><tt>(+ 1 (if (+ 2 -2) (ceiling 6.1) (+ 4 2.3 2)))</tt></p><p>Notice that you're dealing with three distinct types of atomic elements inthese expressions: <em>ints</em>, <em>doubles</em>, and <em>symbols</em>. The<em>ints</em> and <em>doubles</em> are two different types of literals usedas operands. In addition, the operator <em>symbols</em> are functions whosesymbol names are <tt>+</tt>, <tt>if</tt>, and <tt>ceiling</tt>.</p><p>The <tt>+</tt> operator accepts any number of operands to be added. Theoperands can be any mix of ints or doubles. Like in C or C++, the return typeshould be double if any of the operands are double, and int otherwise. If nooperands are given, then the result should be zero which is the identityvalue for addition.</p><p>The <tt>ceiling</tt> operator requires exactly one operand, which must bea double. It returns an int which is the smallest integer that is greater orequal to the operand.</p><p>The <tt>if</tt> operator requires either two or three operands. It firstchecks if the first operand is non-zero. If so, then it should return theresult of evaluating the second operand. Otherwise, it should return theresult of evaluating the third operand (if only two operands were given, thenthe return value is undefined, or in other words, you may return anything youlike).</p><p>Also notice that operands do not have to be literals. They also canrecursively be sub-expressions.</p><p>Given such an input expression, your evaluator should return the result ofevaluating the expression, for example:</p><p><tt>(+ 2 3 4 5)</tt> should return the int <tt>14</tt><br /><tt>(+ 2 3.5)</tt> should return the double <tt>5.5</tt><br /><tt>(+ 2)</tt> should return the int <tt>2</tt><br /><tt>(+)</tt> should return the int <tt>0</tt><br /><tt>(+ (+ -2 5 -1) 3.5)</tt> should return the double <tt>5.5</tt><br /><tt>(ceiling 4.7)</tt> should return the int <tt>5</tt><br /><tt>(ceiling 4.0)</tt> should return the int <tt>4</tt><br /><tt>(ceiling -4.7)</tt> should return the int <tt>-4</tt><br /><tt>(if 5 7 8.3)</tt> should return the int <tt>7</tt><br /><tt>(if 0 7 8.3)</tt> should return the double <tt>8.3</tt><br /><tt>(if (+ 2 3) (ceiling 6.1) (+ 4 2.3 2))</tt> should return the int<tt>7</tt><br /><tt>(if (+ 2 -2) (ceiling 6.1) (+ 4 2.3 2))</tt> should return the double<tt>8.3</tt><br /><tt>(+ 1 (if (+ 2 -2) (ceiling 6.1) (+ 4 2.3 2)))</tt> should return thedouble <tt>9.3</tt></p><p>Your expression evaluator should proceed in two independent stages:</p><ol>  <li><em>Parse</em> the input string to analyze and understand its    structure. The parser should return a tree data structure in which it    records (a) the nested structure of the parenthesized expressions and    sub-expressions, and (b) the types of all the elements in the  expression.</li>  <li><em>Evaluate</em> the expression stored in the tree data structure, by    doing a depth-first traversal. The evaluator should return the value    resulting from evaluating the entire expression.</li></ol><p>If there is any error in the types or number of operands in the inputexpression, your expression evaluator should print the string <tt>ERROR</tt>on standard error (<tt>cerr &lt;&lt; "ERROR"</tt>), and call <tt>exit(1)</tt>to terminate program execution. Otherwise, for this assignment, you mayassume that you will only be tested with input expressions that can safely beparsed.</p><h3>Borrowing someone else's expression parser</h3><p>Thankfully, you don't have to write a parser. You've already found aparser written by someone else, capable of reading and understanding stringsin s-expression format. Download the package at the top of this page,then:</p><p><tt>$ tar xzf a1.tar.gz</tt> <i>// unpack the archive</i><br /><tt>$ cd a1</tt><br /><tt>$ make</tt><br /><tt>g++ -c main.cpp</tt><br /><tt>g++ -c parse.cpp</tt><br /><tt>g++ -c eval.cpp</tt><br /><tt>g++ -c Cell.cpp</tt><br /><tt>g++ -DOP_ASSIGN -o main main.o parse.o eval.o Cell.o -lm</tt><br /><tt>$ main testinput.txt</tt></p><p>You will see the parser's test program run. You can also run the programin interactive mode by typing <tt>main</tt> without any command-linearguments. In interactive mode, the program will prompt you to type in anexpression, and then it'll print the expression back to you, and repeat untilyou type control-D to generate an EOF (end-of-file).</p><p>You wish to re-use this code for parsing s-expressions. The only problemis that this parser, as originally written, does not actually build a treedata structure. So you will need to modify the code to suit the purposes ofthis assignment.</p><p>But you are lucky that the author of the parser encapsulated his codequite neatly. You will not even have to touch his parser code (which is in<tt>parse.hpp</tt> and <tt>parse.cpp</tt>). As the parser analyzes the inputstring, it needs to call various operations to record the nested treestructure that it is finding in the s-expression. The author wiselyencapsulated all these operations and global constants in a separate headerfile <tt>cons.hpp</tt> that keeps all the concrete tree implementationdetails hidden from the parser:</p><ul>  <li><tt>Cell* make_int(const int i)</tt> returns a newly constructed int    cell, i.e., a leaf node initialized to hold the int value <tt>i</tt></li>  <li><tt>Cell* make_double(const double d)</tt> returns a newly constructed    double cell, i.e., a leaf node initialized to hold the double value    <tt>d</tt></li>  <li><tt>Cell* make_symbol(const char* const s)</tt> returns a newly    constructed symbol cell, i.e., a leaf node initialized to hold the symbol    name <tt>s</tt></li>  <li><tt>Cell* cons(Cell* const my_car, Cell* const my_cdr)</tt> returns a    newly constructed cons cell, i.e., an internal node initialized to hold    the two pointers <tt>my_car</tt> and <tt>my_cdr</tt></li></ul><ul>  <li><tt>bool intp(Cell* const c)</tt> returns true iff the cell pointed to    by <tt>c</tt> is an int cell</li>  <li><tt>bool doublep(Cell* const c)</tt> returns true iff the cell pointed    to by <tt>c</tt> is a double cell</li>  <li><tt>bool symbolp(Cell* const c)</tt> returns true iff the cell pointed    to by <tt>c</tt> is a symbol cell</li>  <li><tt>bool nullp(Cell* const c)</tt> returns true iff <tt>c</tt> is is    the null pointer (which is equivalent to the empty list)</li>  <li><tt>bool listp(Cell* const c)</tt> returns true iff the cell pointed to    by <tt>c</tt> is a cons cell, or if <tt>c</tt> is the null pointer (i.e.,    if c points to an empty list)</li></ul><ul>  <li><tt>extern Cell* const nil</tt> holds the value of a null pointer,    which we consider equivalent to an empty list</li></ul><ul>  <li><tt>int get_int(Cell* const c)</tt> returns the value in the int cell    pointed to by <tt>c</tt> (error if <tt>c</tt> is not an int cell)</li>  <li><tt>double get_double(Cell* const c)</tt> returns the value in the    double cell pointed to by <tt>c</tt> (error if <tt>c</tt> is not a double    cell)</li>  <li><tt>string get_symbol(Cell* const c)</tt> returns the value in the    string cell pointed to by <tt>c</tt> (error if <tt>c</tt> is not a string    cell)</li>  <li><tt>Cell* car(Cell* const c)</tt> returns the car pointer of the cons    cell pointed to by <tt>c</tt> (error if <tt>c</tt> is not a cons  cell)</li>  <li><tt>Cell* cdr(Cell* const c)</tt> returns the cdr pointer of the cons    cell pointed to by <tt>c</tt> (error if <tt>c</tt> is not a cons  cell)</li></ul><ul>  <li><tt>ostream&amp; operator&lt;&lt;(ostream&amp; os, Cell* const c)</tt>    prints the cons cell pointed to by <tt>c</tt> to the output stream    <tt>os</tt>, using s-expression notation</li></ul><p>Notice that even though these are just ordinary functions (not memberfunctions of a class), nevertheless this set of functions constitutes aninterface for an abstract data type; we'll discuss more background on thisparticular ADT below. The way that <tt>cons.hpp</tt> specifies the ADTinterface is nice because it makes very few assumptions about how theconcrete implementation might be done. (Good object-oriented programmingstyle does <em>not</em> necessarily require using classes! For example, seeScott Myer's article <a href="http://www.ddj.com/dept/cpp/184401197">HowNon-Member Functions Improve Encapsulation</a>.)</p><p>The file <tt>cons.hpp</tt> that came with the parser just connects all thefunctions to a dummy example implementation of the ADT that makes use of asuper-simple, incomplete <tt>Cell</tt> class probably written by someone else(found in <tt>Cell.hpp</tt> and <tt>Cell.cpp</tt>). As mentioned earlier,this dummy example implementation isn't actually capable of building a treedata structure with pointers and nodes. Instead, it just records thesub-trees using a string encoding, rather than a tree data structure. Most ofthe functions needed by <tt>cons.hpp</tt> aren't even working yet in thedummy <tt>Cell</tt> class, since the basic parser can be run without theaccessor functions <tt>intp</tt>, <tt>doublep</tt>, <tt>symbolp</tt>,<tt>nullp</tt>, <tt>listp</tt>, <tt>get_int</tt>, <tt>get_double</tt>,<tt>get_symbol</tt>, <tt>car</tt> and <tt>cdr</tt>. You can build treeswithout using these accessor functions, although it's not terribly usefulwithout the accessor functions since nobody can access the tree you've built.(And in fact, the string encoding that's used is actually just s-expressionnotation again! Of course this circular set-up is not terribly useful,either; it's just a partial example to show you how to work with the<tt>cons.hpp</tt> ADT interface by connecting it to a concrete implementationin <tt>Cell.hpp</tt>.)</p><p>So the parser author (me) and the tree data structure author (you) bothhave interfaces encapsulating our code, helping us to divide and conquer thework in <em>both</em> directions:</p><ul>  <li><tt>parse.hpp</tt> is the interface that tells you <em>what</em> the    parser can do, while hiding the dirty implementation details of    <em>how</em> the parser works (in my <tt>parse.cpp</tt> which your tree    data structure doesn't get to see).</li>  <li><tt>cons.hpp</tt> is the interface that tells me what the tree data    structure can do, while hiding the dirty implementation details of how    the tree data structure works (in your <tt>Cons.hpp</tt> and    <tt>Cons.cpp</tt> which my parser doesn't get to see).</li></ul><h3>Adapting the parser to this assignment</h3><p>You realize that the cleanest and easiest way to proceed is to leave<tt>cons.hpp</tt> exactly the way it is. That way, you only need to replacethe <tt>Cell</tt> class with your own implementation. (This is good softwareengineering at work, helping you through proper encapsulation!)</p><p>You will also stick to re-using the existing interface of the<tt>Cell</tt> class when implementing your own version of <tt>Cell</tt>; youwon't delete or rename any functions or member functions, to avoid breakingthe parser. (However, you might wish to add some new functions and memberfunctions, to support manipulating and accessing the tree data structure youbuild.)</p><p>Looking at the public interface specified by the <tt>Cell</tt> class in<tt>Cell.hpp</tt>, you see there are a few constructors that the parser's<tt>cons.hpp</tt> will expect your own implementation to provide:</p><ul>
12 3 下一页
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -