Syntax-Directed Translation

发表于

Syntax-Directed Translation

error handling

编译器的两个作用：

  • 检测无效的程序；
  • 翻译有效的程序；

error handler的作用：

  • 准确报告错误；

  • 迅速从错误回复；

  • 不影响有效部分的编译速度；

  • panic mode：

考虑这样的错误：(1++2)+3

panic mode的测量是：跳过，到达下一个整数，然后继续；

  • error productions

分辨出已知的语法错误

error correction：尝试去找出正确的接近的程序，对tokens进行插入和删除；

Abstract Syntax Tree

编译器需要一个数据结构去代表那个程序。

考虑grammar：E->int|(E)|E+E，字符串为5+(2+3)，lexical analysis之后变成int'+'('int'+'int')'，然后parse tree为

img

然后构造AST：

img

强调嵌套结构，更加抽象并且没有non-terminals

Recursive Descent Parsing

也叫top-down parsing，则parse tree是从上到下，从左到右去构建。

考虑grammar：

E->T|T+E T->int | int * T | (E)

token stream为：(int),匹配5个括号

在构造过程中，按照从上到下从左到右一个一个比对，找到正确的parse tree

Recursive Descent Algorithm

首先来看一些特别的tokens：INT,OPEN,CLOSE,PLUS,TIMES，全局的next指向下一个的输入token

定义个函数来检测匹配与否：

  • 对于给定的终止符：**bool term(TOKEN tok){return *next++==tok;}**

  • S中的第n个production：bool Sn(){...}

  • 尝试所有的production：bool S(){...}

  • 对于production：E->T: bool E1(){return T();}

  • 对于production：E->T+E: bool E2(){return T()&&term(PLUS)&&E();}

  • 对于所有的productions of E(带回溯的情况):

1
2
3
4
bool E(){
    TOKEN* save = next;
    return (next=save, E1()) || (next, save, E2()) ;
}
  • non-terminal T:

bool T1(){return term(INT);}

bool T2(){return term(INT)&&term(TIMES)&&T();}

bool T3(){return term(OPEN)&&E()&&term(CLOSE);}

1
2
3
4
bool T(){
    TOKEN* save = next;
    return (next=save, T1()) || (next=save, T2()) || (next=save, T3());
}

如何开始parser:

  • 初始化next指针
  • 调用E()

接下来就可以按照从上到下，从左到右进行parse，如果mismatch就进行回溯。

Left Recursion

  • 考虑这样的production：S->Sa
1
2
bool S1(){return S()&&term(a);}
bool S(){return S1();}

在这种情况下，S()进入了无限递归；

对于一个grammar，若存在P经过一次或者多次的递归，即推导出以P开头的式子，则称之为左递归。

elimination of left recursion

考虑这样的grammar：A→Aa1｜Aa2……｜Aan｜b1｜b2……｜bm

可以改写成：

A→b1A’｜b2A’……｜bmA’

A’ →a1A’｜a2A’……｜anA’｜ε