Parsing arithmetic expressionsReading material: These notes and an implementation (seecourse web page).The best way to prepare [to be a programmer] is to writeprograms, and to study great programs that other peoplehave written. In my case, I went to the garbage cans at theComputer Science Center and fished out listings of theiroperating system. (Bill Gates)First learn computer science and all the theory. Nextdevelop a programming style. Then forget all that and justhack. (George Carrette)Look at this website:GrammarA grammar: set of rules for generating sentences of alanguage.Sentence ::= Noun Verb NounNoun ::= boysNoun ::= girlsVerb ::= likeVerb ::= seeThis grammar has 5 rules. The first says:A Sentence can be a Noun followed by a Verb followedby a Noun.Note: Whitespace between words doesn’t matter.Grammar is boring because the set of Sentences (8) is finite.Example of Sentence:boys see girlsgirls like boysRecursive grammar Sentence::= Sentence and Sentence Sentence::= Noun Verb NounNoun ::= boysNoun ::= girlsVerb ::= likeVerb ::= seeExample of Sentence:boys see girlsgirls like boys and boys see girlsgirls like boys and boys see girls and boys see girlsgirls like boys and boys see girls and boys like girls and boys like girlsGrammar has an infinitenumber of Sentences,because Sentence is definedrecursivelyNotations used in grammarsNotation used to make grammars easier to write: { … } stands for zero or more occurrences of … Example: Noun phrase ::= { Adjective } Noun Meaning: A Noun phrase is zero or more Adjectivesfollowed by a Noun. <b | c> stands for either a b or a c. Example: Expression ::= Term <+ | –> Term Meaning: An Expression is a Term followed by (either + or–) followed by a Term Alternative: Expression is Term + Term or Term – TermGrammar for arithmetic expressionsExpression ::= E $ --$ marks the end of the ExpressionE ::= T { <+ | –> T }T ::= F { <* | /> F }F ::= IntegerF ::= – FF ::= ( E )An E is a T followed by anynumber of things of the form <+ | –> THere are four Es: T T + T T + T + T T + T - T - T + TSyntax treesExpression ::= E $ F ::= IntegerE ::= T { <+ | –> T } F ::= – FT ::= F { <* | /> F } F ::= ( E )ExpressionETF2 $ExpressionET TF2 + 3 $FTreesExpressionET TF2 + 3 $Froot of treeleaf of treeThe node labeled E is theparent of the nodes labeled Tand +. These nodes are thechildren of node E. Nodeslabeled T and + are siblings.Grammar gives precedence to * over +Expression ::= E $ F ::= IntegerE ::= T { <+ | –> T } F ::= – FT ::= F { <* | /> F } F ::= ( E )ETF2 + 3 * 4 2 + 3 * 4ET TF FTF FFTAfter doingthe plusfirst, thetree cannotbecompletedGrammar gives precedence to * over +Expression ::= E $ F ::= IntegerE ::= T { <+ | –> T } F ::= – FT ::= F { <* | /> F } F ::= ( E )ETF2 + 3 * 4 ( 2 + 3 ) * 4ET TF FTF FFTMutualrecursionDefined:E in terms of T,T in terms of F,F in terms of E.FEWriting a parser for the languageExpression ::= E $ F ::= IntegerE ::= T { <+ | –> T } F ::= – FT ::= F { <* | /> F } F ::= ( E )Parser for a language is a program that reads in a string ofcharacters and tells whether it is a sentence of the language ornot.In addition, it might construct a syntax tree for the sentence.We will write a parser for the language of expressions thatappears above.Writing a parser for the languageExpression ::= E $ F ::= IntegerE ::= T { <+ | –> T } F ::= – FT ::= F { <* | /> F } F ::= ( E )The scanner is the part of the program that reads in charactersand produces tokens from them, deleting all whitespace. 22 + 35 * – 46 / 2 $Tokena122Tokena21+Tokena635…Writing a parser for the languageExpression ::= E $ F ::= IntegerE ::= T { <+ | –> T } F ::= – FT ::= F { <* | /> F } F ::= ( E )Scan.getToken() is always you the token being processed.Scan.scan() deletes the token being processed, making the nextone in the input the one being processed, and returns the new one. 22 + 35 * – 46 / 2 $ + 35 * – 46 / 2 $ 35 * – 46 / 2 $ * – 46 / 2 $ – 46 / 2 $Writing a parser for the languageExpression ::= E $ F ::= IntegerE ::= T { <+ | –> T } F ::= – FT ::= F { <* | /> F } F ::= ( E )For E, T, F, write a method with this spec (we show only E): /** Token Scan.getToken() is first token of a sentence for E. Parse it, giving error mess. if there are mistakes. After the parse, Scan.getToken should be the symbol following the parsed E. */ public static void parseE(). 2 + ( 3 + 4 * 5 ) + 6after call parse(), situation is this: 2 + ( 3 + 4 * 5 ) + 6Scan.getToken()Scan.getToken()Writing a parser for the languageE ::= T { <+ | –> T }/** Token Scan.getToken() is first token of a sentence for E. Parse it, giving error mess. if there are mistakes. After the parse, Scan.getToken should be the symbol following the parsed E. */ public static void parseE() {parseT(); while (Scan.getToken() is + or - ) {Scan.scan();parse(T);}}Writing a parser for the languageExpression ::= E $ F ::= IntegerE ::= T { <+ | –> T } F ::= – FT ::= F { <* | /> F } F ::= ( E )We now use the blackboard. You should look at the final program,which is on the course website. Download it and play with it. Partsof it will be discussed in recitation this
View Full Document
Unlocking...