Föreläsning 3: Syntaktisk analys ("parsning")

Kursen Kompilatorer och interpretatorer | Föreläsningar: 1 2 3 4 5 6 7 8 9 10 11 12

Det här är ungefär vad jag tänker säga på föreläsningen. Använd det för förberedelser, repetition och ledning. Det är inte en definition av kursinnehållet, och det ersätter inte kursboken.

Today: How to write a parser by hand

• ALSU-07 avsnitt 2.4 och 2.5
• De två enkla "kompilatorerna" från ASU-86: Program 2.5, och Program 2.9
• Grammatiktransformationer
• (Gamla boken: ASU-86 2.4, 2.5, 2.9)
• (Början på KP kapitel 3)

2.4 Parsing

• Top-down: simpler to build (by hand)
• Bottom-up: harder to build (so we use tools such as Yacc), can handle a larger class of grammars

Top-down parsing (2.4.1)

Example: Types in Pascal.

simple -> integer
simple -> char
simple -> num dotdot num
type -> simple
type -> ^ id
type -> array [ simple ] of type

integer
1..100
^kundpost
array [ integer ] of char
array [ 20..40 ] of 0..3
array [ 1..5 ] of array [ 1..3 ] of 2..5

Tokens:
array [ num dotdot num ] of integer

Top-down parsing, starting with a node for the non-terminal type.
Which of the productions (=rules) should we use? (Answer: type -> array ....)
Why? (Answer: The only production that starts with array.)

"Lookahead symbol" = "current token" = Sw: "aktuell token"

ASU-86 fig 2.15:

ASU-86 fig 2.16:

Predictive parsing (2.4.2)

If always just one production possible to chose: predictive parsing, no backtracking

Recursive-descent parsing

Recursive-descent parsing = the parser is a program with a procedure (in C: "function") for each non-terminal.

void simple() {
  if (lookahead == integer)
    match(integer);
  else if (lookahead == char)
    match(char);
  else if (lookahead == num) {
    match(num); match(dotdot); match(num);
  }  
  else
    error();
}

When we write the function type(), it is not enough to see which tokens occur as the first token in the productions for type (^ and array). Since simple can occur as the first thing in a type, we must also see which tokens occur as the first token in productions for simple.

void type() {
  if (lookahead == integer or lookahead == char or lookahead == num)
    simple();
  else if (lookahead == ^) {
    match(^); match(id);
  }
  else if (lookahead == array) {
    match(array); match([); simple(); match(]); match(of); type();
  }
  else 
    error();
}

FIRST(x) = all possible first tokens in strings that match x.

FIRST(simple) = the set { integer, id, char }
FIRST(^ id) = the set { ^ }
FIRST(array [ simple ] of type) = the set { array }
FIRST(type) = the set { ^, array } + the set FIRST(simple) = the set { ^, array, integer, id, char }

Recursive-descent without backtracking: if the grammar contains two rules...

NT -> something
NT -> somethingelse

When to use empty-productions (2.4.3)

stmt -> begin opt_stmts end
opt_stmts -> stmt_list | empty

Designing a predictive parser (2.4.4)

1. Skriv grammatiken (entydig!)
2. Skriv om grammatiken för att få bort FIRST()-konflikter ocg vänsterrekursion
3. Construct a predictive parser, ignoring the semantic rules/actions.
4. Insert the semantic actions.

Left-recursion (2.4.5)

expr -> expr + term

void expr() {
  if (lookahead == num or lookahead == id)
    expr();
  else
...  

A -> A x | y

into these, which are not left-recursive:

A -> y R
R -> x R | empty

Example: rewrite this left-recursive production:

expr -> expr + term | term

expr -> term rest
rest -> + term rest | empty

First version: An expression is either a term, or you already have an expression (which may contain one or more terms) and we cteaye a new expression by adding a plus sign and a term.

Second version: An expression consists of a term, followed by a rest. This rest can either be empty (so the expression only consisted of that single term), or it consists of a plus sign and a term, followed by yet a rest (which may be empty or can contain one or more terms).