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.

Idag: Att skriva en parser för 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)

Ex: 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

Första versionen: Ett uttryck är antingen en term, eller så har man redan ett uttryck (som kan innehålla en eller flera termer) och gör ett nytt uttryck genom att lägga till ett plustecken och en term.

Andra versionen: Ett uttryck består av en term, följt av en rest. Denna rest kan antingen vara tom (så att uttrycket bara bestod av den där enda termen), eller så består den av ett plustecken och en term, följt av ytterligare en rest (som kan vara tom eller innehålla en eller flera termer).

2.5 A translator for simple expressions

Ex: 2, 2+3, 2-3, 2-3+4+5-6

ASU-86 Fig 2.13/2.19 translation scheme for the program in 2.5:

expr -> expr + term { print('+') }
expr -> expr - term { print('-') }
expr -> term
term -> 0 { print('0') }
term -> 1 { print('1') }
term -> 2 { print('2') }
...
term -> 9 { print('9') }

Rewrite the grammar to eliminate left recursion.
Important: Handle the semantic actions as part of the grammar, when you rewrite it using the left-recursion elimination technique from above, to get the prints done at the right places!

expr -> term rest
rest -> + term { print('+') } rest
rest -> - term { print('-') } rest
rest -> empty
term -> 0 { print('0') }
term -> 1 { print('1') }
term -> 2 { print('2') }
...
term -> 9 { print('9') }

void term () {
  if (isdigit(lookahead)) {
    putchar(lookahead);
    match(lookahead);
  }
  else
    error();
}

void rest() {
  if (lookahead == '+') {
    match('+'); term(); putchar('+'); rest();
  }
  else if (lookahead == '-') {
    match('-'); term(); putchar('-'); rest();
  }
  else
  ;
}

void expr() {
  term(); rest();
}

2.5.4 Simplifying the Translator

2.6 Lexical analysis

For example, when the source being read contains fnord, a call to lexan() will return 259 (which is the value ID, meaning that we have found an identifier), and put (for example) 16 in the variable tokenval, meaning that the identifier that was found is identifier number 16 in the symbol table.

Source code: lexer.c

2.7 Incorporating a symbol table

Source code: symbol.c

2.8 Intermediate Code Generation

Programmet "2.9"

Remember how stack macines work:

• number: push the number on the stack
• The next token is an operator: pop, pop, calculate, push the result on the stack

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