Kiến trúc máy tính và hợp ngữ - Chapter 3: Lexical and syntactic analysis - Syntactic sugar causes cancer of the semicolon. a. perlis

Programming Languages2nd editionTucker and NoonanChapter 3Lexical and Syntactic AnalysisSyntactic sugar causes cancer of the semicolon. A. PerlisContents3.1 Chomsky Hierarchy3.2 Lexical Analysis3.3 Syntactic AnalysisSyntactic AnalysisPhase also known as: parserPurpose is to recognize source structureInput: tokensOutput: parse tree or abstract syntax treeA recursive descent parser is one in which each nonterminal in the grammar is converted to a function which recognizes input derivable from the nonterminal. Program Structure consists of:Expressions: x + 2 * yAssignment Statement: z = x + 2 * yLoop Statements: while (i >} while (nullable.size( ) > oldSize);Check Righthand Side{ boolean allNull = true; for (Symbol t : p.rule( )) if (! nullable.contains(t)) allNull = false; if (allNull) nullable.add(p.nonterminal( ));}Rewrite GrammarAugmented formAbbreviate symbolsReplace meta constructs with nonterminalsTransformed GrammarS → A $A → i = E ;E → T E'E' → | AO T E'AO → + | -T → F T'T' → MO F T'MO → * | /F → F' PF' → | UOUO → - | !P → i | l | ( E )Compute Nullable SymbolsPass Nullable1 E' T' F'2 E' T' F'Left Dependency GraphFor each production:A → V1 ... Vn X wV1, ... Vn nullabledraw an arc from A to X.Note: you also get arcs from A to V1, ..., A to Vn Nonterminal First Nonterminal First A i UO ! - E ! - i l ( P i l ( E’ + - AO + - T ! - i l ( T’ * / MO * / F ! - i l ( F’ ! -Recursive Descent ParsingMethod/function for each nonterminalRecognize longest sequence of tokens derivable from the nonterminalNeed an algorithm for converting productions to codeBased on EBNFT(EBNF) = Code: A → w1 If w is nonterminal, call it.2 If w is terminal, match it against given token.3 If w is { w' }: while (token in First(w')) T(w')4 If w is: w1 | ... | wn, switch (token) {case First(w1): T(w1); break;...case First(wn): T(wn); break; 5 Switch (cont.): If some wi is empty, use:default: break;Otherwisedefault: error(token);6 If w = [ w' ], rewrite as ( | w' ) and use rule 4.7 If w = X1 ... Xn, T(w) =T(X1); ... T(Xn);Augmentation ProductionGets first tokenCalls method corresponding to original start symbolChecks to see if final token is end tokenE.g.: end of file token private void match (int t) { if (token.type() == t) token = lexer.next(); else error(t);} private void error(int tok) { System.err.println( “Syntax error: expecting” + tok + “; saw: ” + token); System.exit(1);} private void assignment( ) { // Assignment → Identifier = Expression ; match(Token.Identifier); match(Token.Assign); expression( ); match(Token.Semicolon);} private void expression( ) { // Expression → Term { AddOp Term } term( ); while (isAddOp()) { token = lexer.next( ); term( ); }}Linking Syntax and SemanticsOutput: parse tree is inefficient One nonterminal per precedence levelShape of parse tree that is importantDiscard from Parse TreeSeparator/punctuation terminal symbolsAll trivial root nonterminalsReplace remaining nonterminal with leaf terminalAbstract Syntax ExampleAssignment = Variable target; Expression sourceExpression = Variable | Value | Binary | UnaryBinary = Operator op; Expression term1, term2Unary = Operator op; Expression termVariable = String idValue = Integer valueOperator = + | - | * | / | ! abstract class Expression { }class Binary extends Expression { Operator op; Expression term1, term2;}class Unary extends Expression { Operator op; Expression term;}Modify T(A → w) to Return ASTMake A the return type of function, as defined by abstract syntax. If w is a nonterminal, assign returned value. If w is a non-punctuation terminal, capture its value. Add a return statement that constructs the appropriate object. private Assignment assignment( ) { // Assignment → Identifier = Expression ; Variable target = match(Token.Identifier); match(Token.Assign); Expression source = expression( ); match(Token.Semicolon); return new Assignment(target, source);} private String match (int t) { String value = Token.value( ); if (token.type( ) == t) token = lexer.next( ); else error(t); return value;}