本文主要是介绍【编译原理】第二章 一个简单的语法制导翻译器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一，语法定义
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();elsethrow 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）两种中间表示形式：树形结构，线性表示形式（特别是"三地址代码"）
这篇关于【编译原理】第二章 一个简单的语法制导翻译器的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
