Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
3. Syntax Analysis
NYU Courant Institute
Compiler Construction (CSCI-GA.2130-001)
Copyright By PowCoder代写 加微信 powcoder
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 1 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Acknowledgments
Adapted from CSCI-GA.2130-001 slides by and .
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 2 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Syntax Definitions Parsers
Context-Free Grammars
Top-Down Parsing
FIRST and FOLLOW Sets Predictive Parsing
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 3 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Syntax Definitions Parsers
Context-Free Grammars
Top-Down Parsing
FIRST and FOLLOW Sets Predictive Parsing
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 4 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Second compilation phase
source program
Lexical Analysis
Syntax Analysis
Semantic Analysis
Intermediate Representation Generator Optimizer
Code Generator Machine-Dependent Code Optimizer
target machine code
Symbol Table
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 5 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
position = initial + rate * 60
scanned into list of tokens:
⟨id,1⟩ ⟨=⟩ ⟨id,2⟩ ⟨+⟩ ⟨id,3⟩ ⟨∗⟩ ⟨num,60⟩
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 6 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
parsed into syntax tree:
⟨id,1⟩ww = ”+
⟨id,2⟩ww ”∗
⟨id, 3⟩ according to precedence rules
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 7 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Some tree-structuring syntax rules:
Block indentation (Python).
Block delimiters like {…} (Java, C).
Grouping like ( … ) (most languages). Algebraic precedence (most languages). Statements vs expressions.
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 8 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Syntax Definitions
Context-Free Grammars
Top-Down Parsing
FIRST and FOLLOW Sets Predictive Parsing
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 9 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
How do we specify language syntax?
Context-free grammars:
Special notation (BNF, Backus-Naur form). Set of rules (productions).
if (x == 2) print(“Yep”); else print(“Nope”);
Corresponds to a rule:
stmt → if (expr) stmt else stmt
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 10 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
How do we specify language syntax?
Context-free grammars:
Special notation (BNF, Backus-Naur form). Set of rules (productions).
if (x == 2) print(“Yep”); else print(“Nope”);
Corresponds to a rule:
stmt → if (expr) stmt else stmt
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 10 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Production rules
if (expr) stmt else stmt 77stmtOO __
production head
production body
“generates”
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 11 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Production rules
stmt → if (expr) stmt else stmt
Nonterminals need more rules to define them. Terminals are well defined and need no more rules.
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 12 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Components of context-free grammar
Set of terminal symbols.
Set of nonterminal symbols.
Set of productions.
The head is a nonterminal.
The body is a sequence of terminals and nonterminals.
One nonterminal chosen as the starting symbol.
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 13 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Example: list grammar
list → list + digit list → list − digit list → digit
digit → 0 digit → 1 digit → 2 digit → 3 digit → 4 digit → 5 digit → 6 digit → 7 digit → 8 digit → 9
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 14 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Example (alternative)
What are the terminals here? + − 0…9
What are the nonterminals? list digit
What does the grammar generate? sums of signed digits
list → list + digit | list − digit | digit digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 15 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Example (alternative)
What are the terminals here? + − 0…9
What are the nonterminals? list digit
What does the grammar generate? sums of signed digits
list → list + digit | list − digit | digit digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 15 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Example (alternative)
What are the terminals here? + − 0…9
What are the nonterminals? list digit
What does the grammar generate? sums of signed digits
list → list + digit | list − digit | digit digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 15 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Example (alternative)
What are the terminals here? + − 0…9
What are the nonterminals? list digit
What does the grammar generate? sums of signed digits
list → list + digit | list − digit | digit digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 15 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Example (alternative)
What are the terminals here? + − 0…9
What are the nonterminals? list digit
What does the grammar generate? sums of signed digits
list → list + digit | list − digit | digit digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 15 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Derivations
Derivation algorithm:
given the grammar (production rules),
begin with the start symbol,
repeatedly replace nonterminals (head) with their bodies,
the generated set of terminals defines the language of that grammar.
Example: How do we derive the string 9 − 5 + 7?
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 16 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Derivations
list→list+digit | list−digit | digit
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Deriving the string 9 − 5 + 7:
list ⇒ list + digit ⇒ list − digit + digit ⇒ digit − digit + digit ⇒ 9 − digit + digit ⇒ 9 − 5 + digit ⇒ 9 − 5 + 7
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 17 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Parse trees
Root is labeled by the start symbol
Interior nodes are nonterminals Leaves are terminals or ε
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 18 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
list→list+digit | list−digit | digit digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Derive a parse tree for the string 9 − 5 + 7.
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 19 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Exercise: unique parse tree
list digit
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 20 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
string → string + string | string − string |0|1|2|3|4|5|6|7|8|9
What about a parse tree for the string 9 − 5 + 7 with this grammar?
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 21 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
A grammar is ambiguous if it has more than one parse tree for the same string of terminals.
string string + string
string − string 2
string string − string
9 string + string
Two parse trees for 9 − 5 + 2. Which is right?
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 22 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Detecting ambiguity
Are any of the following grammars ambiguous?
S→+SS|−SS|a S→S(S)S | ε
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 23 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Detecting ambiguity
Are any of the following grammars ambiguous?
S→+SS | −SS | a notambiguous(hardtosee) S→S(S)S | ε
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 24 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Detecting ambiguity
Are any of the following grammars ambiguous?
S→+SS | −SS | a notambiguous(hardtosee) S→S(S)S | ε ()() ambiguous
In general, determining ambiguity is undecidable. Certain classes are known to be unambiguous.
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 25 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Detecting ambiguity
Are any of the following grammars ambiguous?
S→+SS | −SS | a notambiguous(hardtosee) S→S(S)S | ε ()() ambiguous
In general, determining ambiguity is undecidable. Certain classes are known to be unambiguous.
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 25 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Associativity of operators
How will a language evaluate 9−5−2?
If 5 goes with the ‘−’ on the left: (9−5)−2 we say the
operator is left-associative.
If 5 goes with the ‘−’ on the right: 9−(5−2) we say the operator is right-associative.
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 26 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Associativity of operators
How will a language evaluate 9−5−2?
If 5 goes with the ‘−’ on the left: (9−5)−2 we say the
operator is left-associative.
If 5 goes with the ‘−’ on the right: 9−(5−2) we say the operator is right-associative.
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 26 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Associativity of operators
How do we express associativity in production rules?
Left-associative (9−5)−2: term→term−digit | digit
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Right-associative 9−(5−2):
term→digit−term | digit
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 27 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Associativity in grammars
Right associativity obtained by right-recursive grammars. Left associativity obtained by left-recursive grammars.
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 28 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Precedence of operators
What if the operators are different? 9−5 ∗ 2 Since ‘∗’ takes operands before ‘−’,
’∗’ is said to have higher precedence. Another example: logical operators.
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 29 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Precedence of operators
How to present precedence in productions?
expr→expr+term | expr−term | term term→term∗factor | term/factor | factor
factor → digit | (expr)
The example shows both operator precedence (‘∗’, ‘/’ over ‘+’, ‘−’) and left associativity.
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 30 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Precedence (from lowest to highest) plus associativity:
precedence nonassoc LT, GT;
precedence left SUB, ADD;
precedence left DIV, MUL;
Why are comparisons non-associative? Howdoesa < b < cworkinPython?
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 31 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Precedence (from lowest to highest) plus associativity:
precedence nonassoc LT, GT;
precedence left SUB, ADD;
precedence left DIV, MUL;
Why are comparisons non-associative? Howdoesa < b < cworkinPython?
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 31 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Precedence (from lowest to highest) plus associativity:
precedence nonassoc LT, GT;
precedence left SUB, ADD;
precedence left DIV, MUL;
Why are comparisons non-associative? Howdoesa < b < cworkinPython?
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 31 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Syntax Definitions Parsers
Context-Free Grammars
Top-Down Parsing
FIRST and FOLLOW Sets Predictive Parsing
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 32 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Parsing/syntax analysis
The parser/syntax analyzer task:
We have: set of grammar productions.
We receive: string of tokens (terminals of the grammar). We need: find a parse tree that generates the string.
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 33 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Parser generators
CFG (grammar description)
Parsing algorithm
// Syntax //Semantic token Analyzer parse Analyzer
stream tree Yacc, Bison, CUP.
Parser Generator
Lexical Analyzer
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 34 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Example: parsing
Given these grammar productions:
and this string:
stmt → expr
| if (expr) stmt
| for (optexpr ; optexpr ; optexpr) stmt
| other optexpr → expr | ε
for (; expr ; expr) other
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 35 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Example: parsing
How do we generate this parse tree in a procedural manner?
( optexpr ; optexpr ; optexpr ) stmt
ε expr expr
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 36 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Construction of a parse tree
Three general kinds of parsers:
Universal: from any grammar, but too inefficient.
Bottom-up: identifying the string symbols as terminals, constructing the tree from leaves to root.
Top-down: beginning with the start symbol as the root, constructing the tree from root to leaves.
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 37 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Top-down parsing
Given an input string, top-down parsing is defined as follows: Name the root with the starting (nonterminal) symbol.
Repeat while scanning the input one symbol at a time:
At node N labeled with nonterminal A: select a production for A and construct children at N with the symbols in the production body.
Find the next unexpanded node/nonterminal, typically the leftmost unexpanded nonterminal in the tree.
“select a production for A” is guided by the current input symbol.
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 38 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
Top-down parsing
Given an input string, top-down parsing is defined as follows: Name the root with the starting (nonterminal) symbol.
Repeat while scanning the input one symbol at a time:
At node N labeled with nonterminal A: select a production for A and construct children at N with the symbols in the production body.
Find the next unexpanded node/nonterminal, typically the leftmost unexpanded nonterminal in the tree.
“select a production for A” is guided by the current input symbol.
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 38 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
( optexpr ; optexpr ; optexpr ) stmt
OO OO ; expr ; expr OO
OO OO OO OO
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 39 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
( optexpr ; optexpr ; optexpr ) stmt
OO OO ; expr ; expr OO
OO OO OO OO
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 39 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
( optexpr ; optexpr ; optexpr ) stmt
OO OO ; expr ; expr OO
OO OO OO OO
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 39 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
( optexpr ; optexpr ; optexpr ) stmt
OO OO ; expr ; expr OO
OO OO OO OO
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 39 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
( optexpr ; optexpr ; optexpr ) stmt
OO OO ; expr ; expr OO
OO OO OO OO
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 39 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
( optexpr ; optexpr ; optexpr ) stmt
OO OO ; expr ; expr OO
OO OO OO OO
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 39 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
( optexpr ; optexpr ; optexpr ) stmt
OO OO ; expr ; expr OO
OO OO OO OO
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 39 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
( optexpr ; optexpr ; optexpr ) stmt
OO OO ; expr ; expr OO
OO OO OO OO
Compiler Construction (CSCI-GA.2130-001) 3. Top-Down Syntax Analysis 39 / 191
Context Syntax Definitions Parsers Context-Free Grammars Top-Down Pa
( optexpr ; optexpr ;
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com