Lexical and Syntax Analysis

Introduction

• Language implementation systems analyze source code, regardless of the approach:
  • Compilation (e.g., C++ for large applications)
  • Pure Interpretation (e.g., JavaScript)
  • Hybrid approach (e.g., Java with JIT compilers)
• Syntax analysis (parsing) relies on a formal syntax description (BNF).

Advantages of Using BNF to Describe Syntax

• Provides a clear and concise syntax description.
• The parser can be directly based on the BNF.
• Parsers based on BNF are easy to maintain.

Syntax Analysis

• Two parts:
  • Lexical Analyzer:
    • Low-level.
    • Finite automaton based on regular grammar.
    • Deals with small-scale constructs (names, numeric literals).
  • Syntax Analyzer (Parser):
    • High-level.
    • Push-down automaton based on context-free grammar (BNF).
    • Deals with large-scale constructs.

Reasons to Separate Lexical and Syntax Analysis

• Simplicity: Simpler approaches for lexical analysis.
• Efficiency: Optimization of the lexical analyzer is possible, as it consumes significant compilation time.
• Portability: Lexical analyzer parts may be machine-dependent, but the parser is generally portable.

Lexical Analysis

• A pattern matcher for character strings.
• "Front-end" for the parser.
• Identifies substrings (lexemes) of the source program.
  • Lexemes match a character pattern and are associated with a token.
  • Example: sum is a lexeme; its token may be IDENT.

Lexical Analysis Example

• Consider the assignment statement: result = oldsum - value / 100;

Lexical Analysis (continued)

• Extracts lexemes from input and produces corresponding tokens.
• The lexical analyzer is called by the parser when it needs the next token.
• Three approaches for building a lexical analyzer:
  • Formal description of token patterns (using regular expressions) with a software tool for construction.
  • Design a state transition diagram and implement it.
  • Design a state diagram and hand-construct a table-driven implementation.

State Transition Diagram Design

• Directed graph:
  • Nodes labeled with state names.
  • Arcs labeled with input characters that cause transitions.
  • Arcs may include actions for the lexical analyzer.
• State diagrams represent finite automata.
• A naive state diagram would have a transition from each character to another.

Lexical Analysis (continued) - Arithmetic Expressions

• Focus on recognizing arithmetic expressions, including variable names and integer literals.
• Simplifications:
  • Combine transitions by considering character classes.
    • LETTER class includes all letters.
    • DIGIT class includes all digits.

Lexical Analysis (continued) - Reserved words

• Reserved words and identifiers can be recognized together using a table lookup.
• Table lookup determines if a possible identifier is a reserved word.

Lexical Analysis (continued) - Utility Subprograms

• getChar: Reads the next input character, stores it in nextChar, and determines its class, storing that in charClass.
• addChar: Appends the character from nextChar to the lexeme array.
• getNonBlank: Skips white spaces.
• lookup: Determines if the string in lexeme is a reserved word and returns a corresponding code.

State Diagram Example

• Diagram includes states for identifiers (id), integer literals (int), and operators.
• Transitions based on Letter and Digit character classes.
• Actions like addChar and getChar are performed during transitions.
• Returns lookup(lexeme) for identifiers and Int Lit for integer literals.

Lexical Analyzer Implementation

• A lexical analyzer, lexicalAnalyzer.c, implementation example is shown.
• Output example: (sum + 47) / total is tokenized.
• Tokens and lexemes are identified.

The Parsing Problem (Syntax Analysis)

• Goals:
  • Detect all syntax errors and produce appropriate diagnostics.
  • Error recovery: Return to a normal state of analysis.
  • Produce the parse tree (or a trace) for syntactically correct programs.

The Parsing Problem (continued)

• Two categories of parsers:
  • Top-down:
    • Build the parse tree from the root downward (preorder traversal).
    • Follows a leftmost derivation.
  • Bottom-up:
    • Build the parse tree from the leaves upward.
    • Follows the reverse of a rightmost derivation.
• Useful parsers look only one token ahead in the input.

The Parsing Problem (continued) - TOp-Down

• Top-down Parsers:
  • Given a sentential form $xA\alpha$, the parser chooses the correct A-rule to derive the next sentential form, using the first token produced by A.
  • $x$ is a string of terminal symbols, $A$ is a nonterminal, and $\alpha$ is a mixed string.
  • The most common top-down parsing algorithms:
    • Recursive descent - a coded implementation.

The Parsing Problem (continued) - Bottom-Up

• Bottom-up parsers construct a parse tree from the leaves to the root.
• Given a right sentential form $\alpha$, the parser determines which substring of $\alpha$ is the right-hand side of a grammar rule that must be reduced.
• The most common bottom-up parsing algorithms belong to the LR family.

Bottom-up parsers Example

• Grammar and derivation:
  • $S \rightarrow aAc$
  • $A \rightarrow aA \mid b$
  • $S \Rightarrow aAc \Rightarrow aaAc \Rightarrow aabc$

The Parsing Problem (continued) - Complexity

• Complexity:
  • Parsers for any unambiguous grammar are complex and inefficient ($O(n^3)$, where $n$ is the input length).
  • Reparsing is needed when the parser makes a mistake.
  • Compilers use parsers that work for a subset of grammars but operate in linear time ($O(n)$).

Recursive-Descent Parsing

• A collection of recursive subprograms that produce a parse tree in top-down order.
• Each nonterminal in the grammar has a corresponding subprogram.
• EBNF is ideal for recursive-descent parsers because it minimizes the number of nonterminals.

Recursive-Descent Parsing (continued) - Grammar for Simple Expressions

• Grammar for simple expressions:
  • $\langle expr \rangle \rightarrow \langle term \rangle {(+ \mid -) \langle term \rangle}$
  • $\langle term \rangle \rightarrow \langle factor \rangle {(* \mid /) \langle factor \rangle}$
  • $\langle factor \rangle \rightarrow id \mid int_constant \mid ( \langle expr \rangle )$

Recursive-Descent Parsing (continued) - Coding process

• Coding process:
  • lex puts the next token code in nextToken.
  • For each terminal symbol in the RHS, compare it with the next input token.
    • If they match, call lex.
    • Else, there is an error.
  • For each nonterminal symbol in the RHS, call its associated parsing subprogram.

Recursive-Descent Parsing (continued) - Expr Function Example

• Function expr parses strings generated by the rule: $\langle expr \rangle \rightarrow \langle term \rangle {(+ \mid -) \langle term \rangle}$
• The function expr calls term to parse the first term, then iteratively checks for + or - tokens to parse additional terms.

Recursive-Descent Parsing (continued) - Error Detection

• This particular routine does not detect errors.
• Convention: Every parsing routine leaves the next token in nextToken.
• A parsing function assumes that nextToken contains the code for the leftmost token of the input.

Recursive-Descent Parsing (continued) - Multiple RHS

• A nonterminal with multiple RHS requires an initial process to determine which RHS to parse.
• The correct RHS is chosen based on the next input token (lookahead).
• Compare the next token with the first token that can be generated by each RHS until a match is found.
• If no match is found, it is a syntax error.

Recursive-Descent Parsing (continued) - Term Function Example

• Function term parses strings generated by the rule: $\langle term \rangle \rightarrow \langle factor \rangle {(* \mid /) \langle factor \rangle}$
• The function term calls factor to parse the first factor, then iteratively checks for * or / tokens to parse additional factors.

Recursive-Descent Parsing (continued) - Factor Function Example

• Function factor parses strings generated by the rule: $\langle factor \rangle \rightarrow id \mid int_constant \mid ( \langle expr \rangle )$
• The function factor checks the nextToken to determine which RHS to parse:
  • If ID_CODE or INT_CODE, calls lex.
  • If LP_CODE, calls lex, expr, and checks for RP_CODE.
  • Otherwise, reports an error.

Recursive-Descent Parsing (continued) - Trace Example

• Trace of the lexical and syntax analyzers on (sum + 47) / total.
• Shows the sequence of calls to expr, term, and factor, along with the corresponding token and lexeme.

Parse Tree Example

• Parse tree for (sum+47)/total example.
• Shows the hierarchical structure of the expression.

Recursive-descent Parser with a Java if statement

• Grammar:
  • $\langle ifstmt \rangle \rightarrow if (\langle boolexpr \rangle) \langle statement \rangle [else \langle statement \rangle]$
• The ifstmt function checks for the IF_CODE token, then continues to parse the Boolean expression and the then/else clauses, if present.

Exercises

• Exercises include showing the trace and parse tree for the recursive descent parser for strings like a + b * c and a * (b + c).
• Using the grammar: $\langle expr \rangle \rightarrow \langle term \rangle {(+ \mid -) \langle term \rangle}$, $\langle term \rangle \rightarrow \langle factor \rangle {(* \mid /) \langle factor \rangle}$, $\langle factor \rangle \rightarrow id \mid int_constant \mid ( \langle expr \rangle )$

Solution: a+b*c

• Call lex /* returns a */
• Enter <expr>
• Enter <term>
• Enter <factor>
• Call lex /* returns + */
• Exit <factor>
• Exit <term>
• Call lex /* returns b */
• Enter <term>
• Enter <factor>
• Call lex /* returns * */
• Exit <factor>
• Call lex /* returns c */
• Enter <fctor>

Recursive-Descent Parsing (Limitations) - LL Grammar Class

• The LL Grammar Class
  • Left Recursion Problem
    • If a grammar has left recursion (direct/indirect), it cannot be the basis for a top-down parser (e.g., A -> A+B).
    • Direct left recursion can be removed by transforming the grammar rules.

Recursive-Descent Parsing (Limitations) - Left Recursion Removal

• Left Recursion Removal process:
  1. Group the A-rules as $A \rightarrow A\alpha<em>1 \mid \ldots \mid A\alpha</em>m \mid \beta<em>1 \mid \beta</em>2 \mid \ldots \mid \beta_n$ where none of the $\beta$’s begins with A.
  2. Replace the original A-rules with $A \rightarrow \beta<em>1A’ \mid \beta</em>2A’ \mid \ldots \mid \beta<em>nA’$ and $A' \rightarrow \alpha</em>1A' \mid \ldots \mid \alpha_mA' \mid \epsilon$

Recursive-Descent Parsing (Limitations) - Example

• Original grammar:
  • $E \rightarrow E + T \mid T$
  • $T \rightarrow T * F \mid F$
  • $F \rightarrow (E) \mid id$
• The transformed grammar:
  • $E \rightarrow T E'$
  • $E' \rightarrow + T E' \mid \epsilon$
  • $T \rightarrow F T'$
  • $T' \rightarrow * F T' \mid \epsilon$
  • $F \rightarrow (E) \mid id$

Recursive-Descent Parsing (Limitations) - Pairwise Disjointness

• The other characteristic of grammars that disallows top-down parsing is the lack of pairwise disjointness.
• The inability to determine the correct RHS based on one token of lookahead

Recursive-Descent Parsing (Limitations) - Pairwise Disjointness Test

• Pairwise Disjointness Test:
  • For each nonterminal, A, in the grammar that has more than one RHS, for each pair of rules, A -> ai and A -> aj, it must be true that FIRST(ai) ∩ FIRST(aj) = ∅.
  • Example 1: A -> a | bB | cAb (passes the test).
  • Example 2: A -> a | aB (fails).

Recursive-Descent Parsing (Limitations) - Left Factoring

• In many cases, a grammar that fails the pairwise disjointness test can be modified so that it will pass the test.
• Consider the rule $\langle variable \rangle \rightarrow identifier \mid identifier [\langle expression \rangle]$
• A process called left factoring can be used in this case.
• Two rules can be generated instead: $\langle variable \rangle \rightarrow identifier \langle new \rangle$ and $\langle new \rangle \rightarrow \epsilon \mid [\langle expression \rangle]$

Exercises

• Problem 1: Design a state diagram to recognize one form of the comments of the C-based programming languages, those that begin with /* and end with */.
• Problem 2: Write and test the code to implement the state diagram of Problem 1.

Solutions

• Every arc in this graph is assumed to have addChar attached
• /* fjnekngv 5445 vfnkv *vfbl --*/

Bottom-up Parsing

• The parsing problem is finding the correct RHS in a right-sentential form to reduce to get the previous right-sentential form in the derivation.
• In each step, the task of the bottom-up parser is to find the specific RHS, the handle, in the sentential form that must be rewritten to get the (previous) sentential form

Bottom-up Parsing Example

• Consider the grammar:
  • $E \rightarrow E + T \mid T$
  • $T \rightarrow T * F \mid F$
  • $F \rightarrow (E) \mid id$
• The rightmost derivation example :
  • $E \Rightarrow E + T \Rightarrow E + T * F \Rightarrow E + T * id \Rightarrow E + F * id \Rightarrow E + id * id \Rightarrow T + id * id \Rightarrow F + id * id$

Bottom-up Parsing (continued) - Definitions

• Intuition about handles:
  • Def: $\beta$ is the handle of the right sentential form $\gamma = \alpha\beta w$ if and only if $S \Rightarrow^* \alpha A w \Rightarrow_{rm} \alpha \beta w$
  • Def: $\beta$ is a phrase of the right sentential form $\gamma$ if and only if $S \Rightarrow^* \gamma = \alpha<em>1 A \alpha</em>2 \Rightarrow^+ \alpha<em>1 \beta \alpha</em>2$
  • Def: $\beta$ is a simple phrase of the right sentential form $\gamma$ if and only if $S \Rightarrow^* \gamma = \alpha<em>1 A \alpha</em>2 \Rightarrow \alpha<em>1 \beta \alpha</em>2$
    where $\Rightarrow^*_{rm}$ specifies zero or more rightmost derivation steps and $\Rightarrow^{+}$ means one or more derivation steps.

Bottom-up Parsing (continued) - Phrases

• The leaves of the parse tree in the sentential form $E + T * id$. There are three internal nodes, there are three phrases. Each internal node is the root of a subtree, whose leaves are a phrase.
• The phrases of the sentential form $E + T * id$ are $E + T * id$, $T * id$, and $id$.
• A simple phrase is just a phrase that takes a single derivation step from its root nonterminal node.
• The only simple phrase here is $id$

Bottom-up Parsing (continued) - Handles

• Intuition about handles (continued):
  • The handle of a right sentential form is its leftmost simple phrase
  • Given a parse tree, it is now easy to find the handle
  • Parsing can be thought of as handle pruning

Bottom-up Parsing (continued) - Shift-Reduce Algorithms

• As with other parsers, the input to a bottom-up parser is the stream of tokens of a program and the output is a sequence of grammar rules
• Reduce is the action of replacing the handle on the top of the parse stack with its corresponding LHS
• Shift is the action of moving the next token to the top of the parse stack

Bottom-up Parsing (continued) - LR Parsers

• LR parsers use a relatively small program and a parsing table that is built for a specific programming language
• Advantages of LR parsers:
  • They will work for nearly all grammars that describe programming languages.
  • They can detect syntax errors as soon as it is possible.
  • The LR class of grammars is a superset of the class parsable by LL parsers

Bottom-up Parsing (continued) - Knuth's Insight

• LR parsers must be constructed with a tool
• Knuth’s insight: A bottom-up parser could use the entire history of the parse, up to the current point, to make parsing decisions
  • There are only a finite and relatively small number of different parse situations that could have occurred, so the history could be stored in a parser state, on the parse stack

Bottom-up Parsing (continued) - LR Configuration

• An LR configuration stores the state of an LR parser as a pair of strings
• (stack, input)
• ($S<em>0X</em>1S<em>1X</em>2S<em>2…X</em>mS<em>m, a</em>ia<em>{i+1}…a</em>n$$)
• The \$ sign is used for normal termination of the parser

Structure of An LR Parser

• Diagram of an LR Parser with Parse Stack, Parsing Code, and Parsing Table
• Example Parsing: id1*id2-id3

Bottom-up Parsing (continued) - LR Parser Components

• LR parsers are table driven, where the table has two components, an ACTION table and a GOTO table
  • The ACTION table specifies the action of the parser, given the parser state and the next token
    • Rows are state names; columns are terminals
  • The GOTO table specifies which state to put on top of the parse stack after a reduction action is done
    • Rows are state names; columns are nonterminals

LR Parsing Table

• E -> E+T (R1)
• E -> T (R2)
• T -> T*F (R3)
• T -> F (R4)
• F -> (E) (R5)
• F -> id (R6)

Bottom-up Parsing (continued) - Parser Actions

• Initial configuration: (S0, a1…a_n$)
• Parser actions:
  • For a Shift, the next symbol of input is pushed onto the stack, along with the state symbol that is part of the Shift specification in the Action table
  • For a Reduce, remove the handle from the stack, along with its state symbols. Push the LHS of the rule. Push the state symbol from the GOTO table, using the state symbol just below the new LHS in the stack and the LHS of the new rule as S_0$$

Bottom-up Parsing (continued) - Parser Actions

• Parser actions (continued):
  • For an Accept, the parse is complete and no errors were found.
  • For an Error, the parser calls an error-handling routine.

Bottom-up Parsing (continued) - Table Generation

• A parser table can be generated from a given grammar with a tool, e.g., yacc or bison

Questions - Top- Down vs Bottom-Up

• Briefly discuss what the potential advantages / disadvantages are of bottom-up versus a top-down parser generators
• Bottom-up
  • Harder to debug
  • More expressive
  • Grammar does not need to be modified (as much)
  • Results in more intuitive parse tree structure.
• Top-down
  • Easier to debug and more intuitive
  • Can be implemented manually

Summary

• Syntax analysis is a common part of language implementation
• A lexical analyzer is a pattern matcher that isolates small-scale parts of a program
  • Detects syntax errors
  • Produces a parse tree
• A recursive-descent parser is an LL parser
  • EBNF
• Parsing problem for bottom-up parsers: find the substring of current sentential form
• The LR family of shift-reduce parsers is the most common bottomup parsing approach