【编译原理】第二章 一个简单的语法制导翻译器

一，语法定义

1）文法：对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”），而未
涉及语义问题。

例：有一句子：“我是大学生” 。这是一个在语法、语义上都正确的句子，该句子的结构（称为语法结构）是由它的语法决定的。在本例中它为“主谓结构”

2）文法定义

文法G=（Vn，Vt，P，Z）
Vn：非终结符号集，语法变量
Vt：终结符号集，词法单元
P：产生式或规则的集合
Z：开始符号（识别符号） Z∈Vn

例：if(expression) statement else statement;

关键字if和括号：为 终结符号(词法单元)

expression、statement：非终结符号

3）推导

从一个要识别的符号开始推导,即用相应规则的右部来替代规则的左部,每次仅用一条规则去进行推导。从开始符号出发，不断将某个非终结符号替换为该非终结符号的某个产生式的体。

<句子>::=<主语><谓语>
<主语>::=<代词>|<名词>
<代词> ::=你|我|他
<名词>::= 王民|大学生|工人|英语
<谓语>::=<动词><直接宾语>
<动词>::=是|学习
<直接宾语>::=<代词>|<名词>

4）语法分析

接受一个终结符号串作为输入，找出从文法的开始符号推导出这个串的方法。如果不能从文法符号推到得到该终结符号串，则报错。

5）语法分析树

语法分析树被定义为具有下述性质的一棵树：
1） 根由开始符号所标记；
2） 每个叶子由一个终结符、非终结符、或ε标记；
3） 每个内部结点由一个非终结符标记；
4） 若A是某内部节点的标记，且X1，X2，...，Xn是该节点从左到右所有孩子的标记，则A→X1X2...Xn是一个产生式。若A→ε，则标记为A的结点可以仅有一个标记为ε的孩子。

例子：9-5+2

文法的产生式：list -> list + digit ;

list -> list - digit ;

list -> digit

digit -> 0 | 1| 2| 3| 4| 5| 6| 7| 8| 9

非终结符：list digit list是文法开始符号

终结符：零个或多个终结符号组成的序列，零个终结符组成的串称为空串

语法分析树：

list

/ | \

list | digit

/ | \ | |

list | digit | |

| | | | |

9 - 5 + 2

6）二义性

一个文法可能有多颗语法分析树，生成同一个给定的终结符号。

例子：句子id+id*id可能的分析树

(id+id)*id id+id*id

消除二义性：

① 改写二义文法为非二义文法；
② 规定二义文法中符号的优先级和结合性，使仅产生一棵分析树。

二义文法的优点：
① 比非二义文法容易理解；
② 分析效率高（分析树低，直接推导步骤少）。

三，语法制导翻译

1）属性：与某个程序构造相关的任意的量，属性可以使多种多样的，比如表达式的数据类型、生成的代码中的指令数目或为某个生成的代码中第一条指令的位置。

2）翻译方案：将程序片段附加到一个文法的各个产生式上的表示法。当在语法分析过程中使用一个产生式时，相应的程序片段就会执行。

3）语法制导定义：把①每个文法符号和一个属性集合相关联，并且把②每个产生式和一组语义规则相关联，这些规则用于计算与该产生式中符号相关联的属性值

四，语法分析

1）语法分析：决定如何使用一个文法生成一个终结符号串的过程。原则上语法分析器必须能够构造出语法分析树，否则将无法保证翻译的正确性

2）语法分析分为：自顶向下分析方法和自底向上分析方法

3）自顶向下分析方法：构造方法从根节点开始，逐步向叶子节点方向进行。

4）预测分析法（递归下降分析法）：自顶向下的语法分析方法，使用一组递归过程来处理输入。

五，简单表达式的翻译器

1）抽象语法树：每个内部节点代表一个运算符（而不像语法分析树 为非终结符号）

2）将中缀表达式翻译成后缀表达式：

package demo_parser;
import java.io.*;

public class Demo_Parser {
    static int lookahead;//字节流以整数形式（ascii码中对应十进制数）表示
    public Demo_Parser() throws IOException
    {
        lookahead=System.in.read();//read方法以字节流的方式来读取命令行的输入的数据
    }
    void term() throws  IOException  //如果是数字则输出(不识别字母)
    {
        if(Character.isDigit((char)lookahead))
        {
            System.out.write((char)lookahead);
            match(lookahead);
        }
        else throw new Error("syntax error");
    }
    void match(int t)throws  IOException
    {
        if(lookahead == t)
            lookahead= System.in.read();
        else
            throw new Error("syntax error");
    } 
    void expr() throws IOException
    {
        term();
        while(true)
        {
            if(lookahead =='+')
            {
                match('+');
                term();
                System.out.write('+');
            }
            else if(lookahead == '-')
            {
                match('-');
                term();
                System.out.write('-');
            }
            else return;      
        }
    }
    
    
    public static void main(String[] args) throws IOException{
        
        Demo_Parser parser = new Demo_Parser();
        parser.expr();
        System.out.write('\n');
    }
}

六，词法分析

1）从输入中读取字符，并将它们组成”词法单元对象“。构成一个词法单元的输入字符序列成为词素。

2）剔除空白和注释：实现这个远非易事

3）预读：比如读到 then 还要往下读，如果是空格或其他非标识符则判断为关键字。否则为标识符(thenOther)

<= >= == <>

4）识别关键字和标识符：词法分析采用一个表来保存字符串

七，符号表

1）符号表：一种供编译器用于保存有关源程序构造的各种信息的数据结构。这些信息在编译器的分析阶段被逐步手机并放入符号表。

2）符号表条目：在分析阶段由，词法分析器、语法分析器和语义分析器创建并使用。语法分析器创建。

3）每个作用域设置一个符号表，其作用是将信息从声明的地方传递到实际使用的地方。

八，生成中间代码

1）两种中间表示形式：树形结构，线性表示形式（特别是"三地址代码"）