编译原理 第三章 文法和语言.ppt

2024/8/20课前思考学习目标学习指南难重点知识结构引言和预备知识语法
任何语言程序都可以看成是一定字符集（字母表）上的字符串
语法使得这串字符形成一个形式上正确的程序
语法=词法规则+语法规则
例如：0.5*x1+c
0.5、x1、c、*、+是语言的单词符号
0.5*x1+c是语言的语法单位词法
单词符号
语言中具有独立意义的最基本结构
词法规则
词法规则规定了字母表中哪些字符串是单词符号
单词符号一般包括：常数、标识符、基本字、算符、界限符等
我们用正规式和有限自动机理论来描述词法结构和进行词法分析语法
单词符号
语法单位
表达式、子句、语句、函数、过程、程序
语法规则
规定了如何从单词符号来形成语法单位
现在多数程序语言使用上下文无关文法来描述语法规则
语言的词法规则和语法规则定义了程序的形式结构，是判断输入字符串是否构成一个形式上正确的程序的依据例，对于一个PASCAL程序来说，一个上下文无关文法可以定义
A:=B+C是合乎语法的，
而A:=B+是不合乎语法的。语义
对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义
离开语义，语言只是一堆符号的集合
各种语言中有形式上完全相同的语法单位，含义却不尽相同
对某种语言，可以定义一个程序的意义的一组规则称为语义规则
目前，大多数编译程序使用基于属性文法的语法制导翻译方法来分析语义对于高级程序设计语言及其编译程序来说，语言的语法定义是很重要的。本章主要介绍语法结构的形式描述问题，编译原理的主要内容也可以归纳为应用形式语言理论，并将它贯穿于词法分析和语法分析两个阶段2024/8/202024/8/202024/8/20句子：字母表上符合某种规则构成的串

语言：字母表上句子的集合

注：约定用a,b,c…表示符号；用,,…表示符号串；用A,B,C表示其集合2024/8/20符号串的方幂：设是符号串，把自身连接n次得到符号串，即=…，称为符号串的方幂，写作=n。

符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积（连接）：AB={|A且B}
注：1）串集的自身乘积称作串集的方幂
2）A0={ɛ}

字母表V的n次方幂是字母表V上所有长度为n的串集2024/8/202024/8/20比如：“我是大学生。”是汉语的一个句子
汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语
<句子>::=<主语><谓语>
<主语>::=<代词>|<名词>
<代词>::=我|你|他
<名词>::=王明|大学生|工人|英语
<谓语>::=<动词><直接宾语>
<动词>::=是|学习
<直接宾语>::=<代词>|<名词>2024/8/202024/8/202024/8/202024/8/202024/8/202024/8/202024/8/202024/8/202024/8/202024/8/202024/8/202024/8/20对于例3.1的文法G:S→0S1，S→01，可以给出直接推导的一些例子如下：
v=0S1，w=0011，直接推导：0S10011，使用的规则：S→01，这里=0，=1。
v=S，w=0S1，直接推导：S0S1，使用的规则：S→0S1，这里=，=
v=0S1，w=00S11，直接推导：0S100S11，使用的规则：S→0S1，这里=0，=1。对于例3.2的文法G，直接推导的例子有：
v=<标识符>，w=<标识符><字母>，直接推导：<标识符><标识符><字母>，使用的规则：<标识符>→<标识符><字母>，这里γ=δ=ε
v=<标识符><字母><数字>，w=<字母><字母><数字>，直接推导：<标识符><字母><数字><字母><字母><数字>，使用的规则：<标识符>→<字母>。这里γ=ε，δ<字母><数字>。
v=abc<数字>，w=abc5，直接推导：abc<数字>abc5,使用的规则：<数字>→5，这里γ=abc，δ=ε2024/8/20对例3.1的文法，存在直接推导序列v=0S100S11000S11100001111=w，
即0S100001111，也可记作0S100001111
对例3.2的文法，存在直接推导序列v=<标识符><标识符><数字><字母><数字>x<数字>x1=w，
即<标识符>x1，也可记作<标识符>x12024/8/202024/8/202024/8/202024/8/202024/8/202024/8/200型文法（短语文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的
1型文法（上下文有关文法）：设G=(VN，VT，P，S)