Context-Free Grammars

• Syntax analysis involves recognizing syntactic structure in a token stream and producing a parse tree that represents the structure of the input program.

Regular Expressions

• Regular expression macros can be used for summation expressions; an input of "10+2+30" is valid using digits = [0-9]+ & sum = ({digits} "+")* {digits}
• Regular expressions cannot describe an input like "10+(2+30)", as it is not a regular language.

Context-Free Grammars

• A context-free grammar is similar to regular expressions but include recursion for added functionality.
• Top-level alternation translates into aux = c | d & expr = a b aux e where expr = a b (c | d) e.
• Kleene closure translates into expr = a b c expr & expr = ε where expr = (a b c)*

Key Components

• Terminal symbols (tokens) are fundamental units recognized by the scanner.
• Non-terminal symbols represent higher-level syntactic constructs.
• Start symbol is the initial non-terminal from which derivations begin.
• Grammar rules have the form N -> X*, where N is a non-terminal, and X is a terminal or non-terminal.

CFG Syntax Variants

• BNF (Backus-Naur Form) was developed for Algol-60; ::= 'if' 'then' | ...
• EBNF (Extended Backus-Naur Form) has uses square brackets for optional parts [ ... ] and curly brackets for repetition zero or more times { ... }.
• Scheme Reports (R6RS) utilizes ellipses (...) for repetition zero or more times.

Grammar Notation

digit = 0
...
digit = 9
digits = digit
digits = digit digits
sum = expr "+" sum
sum = expr
expr = digits
expr = "(" sum ")"

Recursion

• Right-recursive grammar: N -> t & N -> t N
• Left-recursive grammar: N -> t & N -> N t

Example grammar

S -> S ; S S -> id := E S -> print ( L ) E -> id E -> num E -> E + E E -> ( S , E ) L -> E L -> L , E

Lists of Expressions

• Left-recursive version: L -> E & L -> L , E
• Right-recursive version: L -> E & L -> E , L
• Ambiguous version L -> E & L -> L , L

Grammar Rule Styles

• Left-recursive rules are preferable for left-associative operators and do not work with top-down parsers; the cost is O(n).
• Right-recursive rules are compatible with both top-down and bottom-up parsers; the cost is O(n).
• Ambiguous rules results in multiple possible parse trees; the cost is O(n³), supported by Earley parser & GLR parser.

Grammar Classes

• LL(k): Left-to-right, Left-most derivations, k tokens lookahead
• LR(k): Left-to-right, Right-most derivations, k tokens lookahead

Technologies

• LL(0) is the simplest top-down parser.
• LL(1) is a typical handwritten recursive-descent parser.
• LL(k) represents parsers generated by a top-down parser generator.
• LR(0) is the simplest bottom-up parser.
• SLR is the simplest bottom-up parser with 1 token lookahead.
• LALR(1) is using a bottom-up parser generator.
• LR(1) is a bottom-up parser with 1 token lookahead.

Concrete Parse Trees

• Concrete Parse Trees represents syntactic structure of input and summarizes how the input was parsed.
• Leaves are terminal symbols (tokens), interior nodes are non-terminal symbols, and the root is the start symbol.
• Reading leaves left-to-right produces the input.

Ambiguous Grammars

• Ambiguous grammars can produce multiple parse trees for the same input.

Derivations

• Derivations start with the start symbol and replace non-terminals with the right-hand side (RHS) of grammar rules until a terminal string is derived.
• Used to define language described by grammar; language is set of all possible strings that can be derived from start symbol.
• Left-most derivations expand the left-most non-terminal by RHS of grammar rule and corresponds to top-down (LL) parsing.
• Right-most derivations expand the right-most non-terminal by RHS of grammar rule and corresponds to bottom-up (LR) parsing.

Abstract Parse Treees

• Represents syntactic structure of input and do not summarize how the input was parsed.

Ambiguous Expression Grammar

• This grammar is convenient and compact:

E -> id E -> num E -> E * E E -> E / E E -> E + E E -> E - E E -> ( E )

Desired Parse Trees

• Higher-precedence operators should be below lower-precedence operators. The right tree for 1-2*3 is prefered.
• For operators with equal precedence, parse trees should reflect associativity. The left parse tree for 1-2-3 reflects (1-2)-3.
• Parentheses do not need representation in the parse tree and are implicit in tree structure.

Unambiguous Expression Grammar

E -> E + T E -> E - T E -> T T -> T * F T -> T / F T -> F F -> id F -> num F -> ( E )

• Lower-precedence operators are at the top.
• Left recursion corresponds to left-associative operators.
• Necessary for handwritten parsers.
• C, C#, and Java have 15 precedence levels, while C++ has 17.

Ambiguous Grammar

• The grammar is ambigious for two nested if-statements (aka. a dangling else); should "else" belong to the inner or outer "if".

S -> if E then S else S
S -> if E then S
S -> other

Unambiguous Grammar

• M: matched statement (each if comes with an else) & U: unmatched statement.

S -> M
S -> U
M -> if E then M else M
M -> other
U -> if E then S
U -> if E then M else U

• The "then" part is matched, therefore each "else" goes with the inner "if".
• LR parsers automatically repair the ambiguous if-statement grammar.

JavaCUP Precedence Directives

precedence nonassoc EQ, NEQ; precedence left PLUS, MINUS; precedence left TIMES, DIV; precedence right EXP; precedence left UMINUS; exp ::= INT | exp PLUS exp | exp MINUS exp | exp TIMES exp | MINUS exp %prec UMINUS ;

Comparison Operators

• In Tiger, comparison operators are non-associative and enforced with a rewrite.
• Java, consecutive comparison operators can result in a type error.
• In C and C++, comparison operators are left-associative.

Assignment Operators

• In the C family, the assignment operator is right-associative and returns the value of the right hand side (RHS).
• Tiger does not allow assignments inside expressions.

Parse Trees in JavaCUP

• Not every grammar rule needs a constructor call

Exp ::= LPAREN SeqExp:e RPAREN
{: RESULT = e; :}
;

-  SeqExp represents a sequence of expressions separated by commas.

• When constructing lists, an empty list might be represented as null

::=
|
{: RESULT = null; :}
Xs:1
{: RESULT = 1; :}
;

• Xs is a list of one or more X's with/without a separator.

LR Parse Engine

• Employs a stack and DFA
  • A DFA is applied to the stack where edges are labeled with (non-)terminals.
• Actions are performed via the following commands: shift/reduce go to state, or accept (end of file - EOF) or reject.

LR Parse Actions

• Conceptually, a shift moves a token from the input onto the stack.
• Reduce(+goto) replaces the RHS of a rule on top of the stack by the LHS.
• Actually, the stack contains DFA state numbers, not tokens or non-terminals.
• Shift and goto put state numbers onto the stack

Parse Table

• The goto-table is to the right, the rest is the parse table.
• $ indicates EOF
• The parse table is for an LALR(1) or LR(1) parser
• The stack stores states, and when parsing a token the parser looks up the action to perform based on the state on top of the stack for the input token.
• An LR(0) parser decides whether to shift or reduce based on the stack content alone before looking at the input token; the parse table uses same reduce action in each column.

Parse Conflict

• Parse conflicts occur if the table construction algorithm results in two actions in the same table slot. CUP handles shift-reduce conflicts and reduce-reduce conflicts using rule order.

Grammar Rule

• Grammar rule with dot is a parser configuration. Everything left of the dot is on the stack; everything right of the dot is on the input. Java CUP shows lookahead tokens for parser configurations.

Parse Actions

Shift(n)

• Eat one token
• Shift state n onto the stack Reduce(k)
• Pop n states off the stack, where n is number of symbols on RHS of rule k
• In a state, look up X (LHS of rule k) to find goto(m) in goto table to find.
• Push state m onto the stack

Conflicts

• Push decision to semantic analysis since there are incorrect expressions in the parser

stm ::= ID ASSIGN E;
E
::= E OR E
E AND E
E EQUAL E
E PLUS E
ID;

• Push decision to Scanner because C++ has ambiguous contexts; needs type info from semantic analysis to be fed back to scanner, or requires lookahead on token stream if type info not available.

Operators

• Use precedence declarations for operators

precedence left PLUS;
precedence right ASSIGN;
precedence nonassoc EQUAL;

• Use %prec if there are no appropriate operators

precedence left UMINUS;
E ::= MINUS E %prec UMINUS;

Conflict Resolution

• Shift/Reduce Conflict in Tiger is fixed by unrolling recursion for Var, ID before LBRACK should not be reduced to Var.
• Parse Conflicts for Declarations in Tiger are solved by structuring grammar to allow correct constructor calls, avoid R/R. Goal: S/R that is automatically resolved via shift preference.
• Solution is to "give preference to DOT in QualName".
• Modify grammar or use precedence declarations.

Error Recovery

• All empty entries in parse tables result in "Syntax error". The default behavior is to stops after the first error.

Error Reporting

• Use grammar rules with special error token.
• Error recovery reports the parse error, pops stack until there is a shift on error, and then discards the input until non-error at which point parsing is resumed.

Error Reporting

• Use grammar rules with special error token.
• Error recovery after reporting parse error includes popping stack until there is a shift on error, shift error token, and discarding input until a state with non-error action, then resume parsing
• Easier with synchronizing token following error but too many error recovery rules lead to S/R and R/R parse conflicts.

Error recovery example

E -> ID
E -> E + E
E -> ( E )
E -> ( error )
Es -> E
Es -> Es ; E
Es > error ; E

• Reports syntax error, "ID+" is deleted from stack, since with "(" on stack, error token shifts. "+ ID" is then removed from input, since "(error must be followed by )" so parser continues.
• Can use grammar rules for reporting semantic errors:

Decl ::= Type ID LBRACK INT RBRACK
ASSIGN LBRACE Exp RBRACE SEM
{: ... :}
| Type ID LBRACK INT RBRACK
ASSIGN LBRACE RBRACE SEM
{:
error("empty array initializer");
RESULT = null;
:}

Error Repair

• Global error repair with a let statement:

let type a := intArray[10] of 0;

1. Error production: delete type ... 0
2. Local repair: replace := with =
3. Global repair: replace type with var

Burke-Fisher

• Use single-token insertions/deletions/substitutions in the last K tokens where the repair farthers the parse by R tokens. K+N*K
• Use semantic actions for insertions

%value ID ("bogus")
%value INT (1)
%value STRING ("")
· Programmer-specified substitutions
%change EQ -> ASSIGN
| ASSIGN -> EQ
| SEM ELSE -> ELSE
|--> IN INT END

• Most bottom-up parser generators build LALR(1) parsers and merge states only distinguished by lookahead.

LR Parser Technologies

• LR(O): parse table construction and parser don't use lookahead
• SLR: Uses the LR(O) parse table construction, reduces lookahead only if it is in the FOLLOW set for LL parsing.
• LALR(1): parse tables uses compressed LR(1).
• LR(1): parse table construction, and use one token lookahead.
• Burke-Fisher requires more data structure; Old stack: parse stack for stack content more than K tokens in the past, Token queue of K tokens, Current stack: parse stack including those K tokens; costs for window size K and and N tokens can be calculated via deletions K+(NK), insertions K+(NK), and substitutions K+(N*K).

Recursive Descent Parsing

void S() {
	switch (tok) {
		case IF:
			eat(IF);
			E();
			eat(THEN);
			S();
			eat(ELSE);
			S();
			break;
		case BEGIN:
			...
		default: error();
} }

• Corresponds to grammar structure of the language. Has Concatenation in grammar corresponds to straight-line code with alternation in grammar corresponds to if-then-else or switch statements

Recusrive Descent Parsing

• "tok" is a variable for the current token 1 Assume one token lookahead; var tok before returns, function eat () also checks it prior to getting next token 2 Each parse function returns a parse tree, and parse tree constructors are called in return statements of parse functions
• Recursive Descent parsing has both Left recursion and common left factors, and solved by restructuring grammar to change from left recursion to right recursion, and restructuring grammar to remove common left factors.

Computing Sets

• Translate Grammar into Code with X-> Y |Z must choose alternatives based on the look ahead and need knowledge of the sets of terminals that "YZ" can start. If considering following grammars, an empty RHS then those sets will also need knowledge of teriminals that can follow X, after the empty RHS Nullabe(X) - "Can X derive the empty string?" FIRST(X) - "Start with terminal" FOLLOW(X) - "Follow Terminal"

Predictive parsers

• Construction of Predictive Parser table requires the user to do

1. First enter production for each given grammar rules such as X-> Y
2. Column T
3. FOLLOW sets must also include "$", also IF if the table contains multiple productions, the grammar is not LL(1) - LL parse table can be translated into recursive-descent code or for use in table-driven parser

X-> Y
		|Z
 Y-> 
     |C
 X-> Y
      |a

- Grammar is not LL(1)

Single Pass Compilation

• Type ID Param is Single-pass vs. multi-pass compiler must be semantic analysis vs main calls as a single vs multi

FunDec:: = Types ID Params
{
	ad Params into symta LBRACE StmtList RBRACE { type-check body generate code
}

Summary Includes

• In Short, Bottom-up parsing is table driven due to the Push automate
• Top-down parsing has recursion, predictive and grammar classes of LL
• Parse has content-free syntax.

Explore syntax analysis using context-free grammars in programming. Learn about terminal, non-terminal, and start symbols. Understand the concept of regular expressions and their limitations in describing complex inputs.