编译原理 文法

本次课程设计主要是介绍LL(1)文法的一般原理，根据给定的一文法编制调试LL(1)文法语法分析程序，以便对任意输入的符号串进行分析。

本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析的理解，加深对自顶向下语法分析方法的认识。

具体如下：1、对语法规则有明确的定义；2、编写的分析程序能够对给定文法进行正确的语法分析；3、对输入给定的文法，手工计算First、Follow集合以及各产生式的Select 集合，再根据Select集合构造出预测分析表；4、对于输入串，应能根据预测分析表判断识别该输入串是否为给定文法的句子；5、对于遇到的错误，给出简单的错误信息提示，保证能够顺利完成语法分析过程。

前言------------------------------------------------------------- Ⅰ目录------------------------------------------------------------- Ⅱ一、系统分析------------------------------------------------------ 11.1 判断LL(1)文法---------------------------------------------- 11.2 构造预测分析表---------------------------------------------- 1二、系统设计------------------------------------------------------ 22.1 基本设计---------------------------------------------------- 22.2 程序流程图-------------------------------------------------- 2三、系统实现------------------------------------------------------ 33.1 程序主要函数------------------------------------------------ 33.2 程序主要代码------------------------------------------------ 3四、系统测试------------------------------------------------------ 7五、总结---------------------------------------------------------- 8 参考文献---------------------------------------------------------- 9一、系统分析有文法G[E]：E->TG T->FSG->+TG|ε S->*FS|ε F->(E)|i 1.1 判断LL(1)文法当我们需选用自顶向下分析技术时，首先必须判别所给文法是否是LL(1)文法，分析所给文法可知文法中不含左公因子，也不存在左递归，因而再对给定文法计算First 集、Follow 集以及Select 集，对于求出的每个产生式的Select 集，看对于同一个左部非终结符是否存在交集，如果它们的交为空则表示所给文法是LL(1)文法，否则不是L(1)文法。

第3章文法和语言第1题文法G＝({A,B,S},{a,b,c},P,S)其中P为：S→Ac|aBA→abB→bc写出L(G[S])的全部元素。

答案：L(G[S])={abc}第2题文法G[N]为：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？答案:G[N]的语言是V+。

V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD....=>NDDDD...D=>D......D或者：允许0开头的非负整数？第３题为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。

答案：G[S]:S->S+D|S-D|DD->0|1|2|3|4|5|6|7|8|9第4题已知文法G[Z]：Z→aZb|ab写出L(G[Z])的全部元素。

答案：Z=>aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbbL(G[Z])={anbn|n>=1}第5题写一文法，使其语言是偶正整数的集合。

要求：(1)允许0打头；(2)不允许0打头。

答案：(1)允许0开头的偶正整数集合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允许0开头的偶正整数集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|0第6题已知文法G：<表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i试给出下述表达式的推导及语法树。

（５）i+(i+i)（６）i+i*i答案：(5)<表达式>=><表达式>＋<项>=><表达式>＋<因子>=><表达式>＋（<表达式>）=><表达式>＋（<表达式>＋<项>）=><表达式>＋（<表达式>＋<因子>）=><表达式>＋（<表达式>＋i）=><表达式>＋（<项>＋i）=><表达式>＋（<因子>＋i）=><表达式>＋（i＋i）=><项>＋（i＋i）=><因子>＋（i＋i）=>i＋（i＋i）(6)<表达式>=><表达式>＋<项>=><表达式>＋<项>*<因子>=><表达式>＋<项>*i=><表达式>＋<因子>*i=><表达式>＋i*i=><项>＋i*i=><因子>＋i*i=>i＋i*i<表达式><表达式>+<项><因子><表达式><表达式>+<项><因子>i<项><因子>i<项><因子>i（)<表达式><表达式>+<项><项>*<因子><因子>i<项><因子>ii第7题证明下述文法G[〈表达式〉]是二义的。

编译原理文法类型介绍辽宁师范大学 王 欣自1956年，乔姆斯基建立了形式语言的描述，使得形式语言的理论发展得十分迅速。

形式语言的理论不仅对计算机科学有着深远的影响，也对编译方法、程序设计语言的设计等方面有着更重大的作用。

乔姆斯基将文法分为0型，1型，2型，3型，本文重点介绍这四种文法的分类与判别条件。

1 文法说明文法G定义为一个四元组（V N，V T，P，S）（肖军模，程序设计语言编译方法：大连理工大学出版社，1991；何炎祥，伍春香，计算机专业不需要编译原理课程吗：计算机教育，2009）：V N表示非终结符集合，非终结符集合包括大写字母、语法实体、变量、小写的斜体字符串及用字母表示的开始符号等。

V T表示终结符集合，终极符包括小写英文字母、数字及不用尖括号括起来的是终极符。

P表示为产生式（α→β）的集合，满足条件且其中至少要包含一个非终结符，，其中（α→β）的意义为α定义为β。

S是一个终极符，作为文法的开始符号，又称作标识符，要求S至少要作为P其中一条产生式的左部出现。

要求V N，V T，P都为非空的有穷集合（冯博琴，编译原理辅助教程：西安交通大学出版社，1995）。

2 文法类型介绍2.1 0型文法2.1.1 0型文法定义设文法，若文法中的每一个产生式都满足条件并且其中至少要包含一个非终结符，同时满足，那么可判定G为一个0型文法（张志红，朱晨光，编译原理中的文法及二义性研究：河南科技，2009）。

例如：2.1.2 0型文法说明0型文法又可被称为短语文法，0型文法的充分必要条件为递归可枚举集必然是一个0型文法。

图灵机等价于0型文法。

图灵机是一个抽象的机器，将一个无限长的纸条分割成一块块小格，且每个小格所表示的颜色不同，机器头在纸带上来回移动，每次读入一个当前的方格信息，结合内部程序将结构输出到纸带方格上，然后移动到其他的方格，继续上述过程。

2.2 1型文法2.2.1 1型文法定义设文法，如果P产生式集合中的每一个产生式（α→β）都满足条件，仅除外，那么当前文法G为1型文法。

编译原理——关于⽂法、推导、规约、句柄、语法树、⼆义性的理解短语：直观理解，该句型中的⼀个符号串，这个符号串能被前⾯句型中的某个⾮终结符推出，那么这个符号串是该句型的短语。

注意必须保证⾮终结符是前⾯句型的，说明要确定⼀个句型的短语，要找到句型对应的推导，规约或语法树才可以，对应的是这个句型⽣成的动态过程。

简单短语：略句柄：⼀个句型只能有⼀个句柄。

（前提默认⾮⼆义性⽂法）推导和规约过程理解推导过程：对每⼀个句型，该句型⼀定有⼀个推导过程（可能不唯⼀），推导过程⼀定对应⼀颗语法树（推导过程可能不唯⼀，当然语法树也可能不唯⼀）推导不唯⼀，规约不唯⼀，规范推导规范推导：最右推导，每次拆最右边的⾮终结符规约过程：规约直观理解就是，“剪⼦树（但留⼦树的根）【对应到表达式就是⽤短语替代那个⾮终结符】，每剪⼀次对应⼀次规约，直到剪到只剩树根”规范规约：最左规约，每次对最左简单短语进⾏的规约⼀个⽂法的句型，必能通过⼀次⼀次的规范推导获得。

同时也能通过⼀次⼀次的规范规约规约⾄开始符号，每次规约都对应⼀个句柄。

所以⽤规约简单短语的⽅法检查⽂法是可⾏的。

规范推导和规范规约互为逆过程：规范推导倒着看就是规范规约规范句型：由规范推导或规范规约得到的句型⼆义性⽂法——不可判定的⽂法所定义的某个句⼦存在两棵不同的语法树。

⽂法中存在某个句⼦，它有两个不同的规范（最右）推导。

⽂法中存在某个句⼦，它有两个不同的规范（最左）规约，即在规约中某些规范句型的句柄不唯⼀。

注意：1. 如果存在两种推导，那么不能说明⼀定是⼆义性⽂法，因为两种推导可能对应同⼀个语法树2. ⼆义性的例⼦句型E+E*i存在不同句柄题型：给⼀句型，找短语、简单短语、句柄1. 画语法树2. 对于某个句型的语法树，它的每⼀颗⼦树都能找出⼀个短语（可能重复），枚举所有的⼦树就能找全。

3.。

编译原理(第二版)第3章文法和语法编译原理(第二版)第3章文法和语法课件第3章文法和语言教学要求：本章是编译原理课程的理论基础，要求理解文法、语言、规范推导、规范归约和短语、简单短语、句柄的基本概念；掌握语言的求解方法、文法的二义性的判断方法及句型的分析方法。

教学重点：上下文无关文法，语言定义编译原理(第二版)第3章文法和语法课件一、语言语言是由句子组成的集合，是由一组记号所构成的集合。

汉语--所有符合汉语语法的句子的全体英语--所有符合英语语法的句子的全体程序设计语言--所有该语言的程序的全体编译原理(第二版)第3章文法和语法课件二、文法一种语言描述工具，用来定义句子的结构，用有限的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。

〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉|〈名词〉〈代词〉::= 你| 我| 他〈名词〉::= 王明| 大学生| 工人| 英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::= 是| 学习〈直接宾语〉::=〈代词〉|〈名词〉“我是大学生”是否是该语言的句子？编译原理(第二版)第3章文法和语法课件〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉|〈名词〉〈代词〉::= 你| 我| 他〈名词〉::= 王明| 大学生| 工人| 英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::= 是| 学习〈直接宾语〉::=〈代词〉|〈名词〉〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生编译原理(第二版)第3章文法和语法课件三、符号和符号串任何一种语言可看成是某个符号集上定义的，按一定规则构成的一切基本符号串组成的集合。

字母表:元素的非空有穷集合。

(符号集) 符号：字母表中的元素。

例如：汉语的字母表中包括汉字、数字及标点符号等。

C语言的字母表是由字母、数字、若干专用符号及IF、FOR之类的保留字组成。

第二章文法和语言本章讲述目前广泛使用的上下文无关文法。

即用上下文无关文法作为程序设计语言语法的描述工具。

阐明语法的一个工具是文法。

本章将介绍文法和语言的概念。

本章重点：上下文无关文法及其句型分析中的有关问题。

第一节文法的直观概念当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。

以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明（或者定义）句子的组成结构，比如：“我是大学生”。

是汉语的一个句子。

汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则：〈句子〉∷＝〈主语〉〈谓语〉〈主语〉∷＝〈代词〉|〈名词〉〈代词〉∷＝我|你|他〈名词〉∷＝王明|大学生|工人|英语〈谓语〉∷＝〈动词〉〈直接宾语〉〈动词〉∷＝是|学习〈直接宾语〉∷＝〈代词〉|〈名词〉“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。

这些规则成为我们判别句子结构合法与否的依据。

一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。

我们开始去找∷＝左端的带有〈句子〉的规则并把它表示成∷＝右端的符号串，这个动作表示成：〈句子〉⇒〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应的规则∷＝右端代替之。

比如，选取了〈主语〉,并采用规则〈主语〉∷＝〈代词〉，那么得到：〈主语〉〈谓语〉⇒〈代词〉〈谓语〉，重复做下去，我们得到句子：“我是大学生”的全部动作过程是：〈句子〉⇒〈主语〉〈谓语〉⇒〈代词〉〈谓语〉⇒我〈谓语〉⇒我〈动词〉〈直接宾语〉⇒我是〈直接宾语〉⇒我是〈名词〉⇒我是大学生符号⇒的含义是，使用一条规则，代替⇒左边的某个符号，产生⇒右端的符号串。

显然，按照上述办法，不仅生成“我是大学生”这样的句子，还可以生成“王明是大学生”，“王明学习英语”，“我学习英语”，“他学习英语”，“你是工人”，“你学习王明”等几十个句子。

⽂法的分类【编译原理】编译原理4种⽂法类型1956年，Chomsky建⽴形式语⾔的描述。

通过对产⽣式的施加不同的限制，Chomsky把⽂法分为4种类型 ⾸先定义⼀个产⽣式 α→β0型⽂法定义：0型⽂法(PSG)：α∈(V N∪V T)* ，且⾄少含⼀个V Nβ∈(V N∪V T)*对产⽣式没有任何限制例如：A0→A0 , A1→B0型⽂法说明：0型⽂法也称为短语⽂法。

⼀个⾮常重要的理论结果是，0型⽂法的能⼒相当于图灵机（Turing）。

或者说，任何0型语⾔都是递归可枚举的；反之，递归可枚举集必定是⼀个0型语⾔。

对0型⽂法产⽣式的形式作某些限制，以给出1，2和3型⽂法的定义。

（注意）⽂法G 定义为四元组（V N ,V T ,P,S）¨V N：⾮终结符集¨V T：终结符集¨P ：产⽣式集合（规则集合）¨S ：开始符号（识别符号）1型⽂法（上下⽂有关⽂法context-sensitive）： 对任⼀产⽣式α→β，都有|β|>=|α|，仅仅 S→ε除外 产⽣式的形式描述：α1Aα2→α1βα2 (其中，α1、α2、β∈（V N∪V T）*，β≠ε，A∈VN) 即：A只有出现在α1α2的上下⽂中，才允许⽤β替换。

产⽣的语⾔称“上下⽂有关语⾔”但S不能出现在产⽣式的右部。

例如：0A0→011000 1A1→1010112型⽂法(CFG)：对任⼀产⽣式α→β，都有α∈V N，β∈（V N∪V T）* 产⽣式的形式描述：A→β(A∈V N) 即β取代A时，与A所处的上下⽂⽆关。

产⽣的语⾔称“上下⽂⽆关语⾔” 例如：G[S]：S→01 S→0S13型⽂法(RG)：也称正规⽂法 每个产⽣式均为 “A→aB”或“A→a” —— 右线性 “A→Ba”或“A→a” —— 左线性 其中，A、B∈V N，a∈V T* 产⽣的语⾔称“正规语⾔” 例如：G[S]： S→0A | 0 A→1B | B B→1 | 04个⽂法类的定义是逐渐增加限制的，因此每⼀种正规⽂法都是上下⽂⽆关的，每⼀种上下⽂⽆关⽂法都是上下⽂有关的，⽽每⼀种上下⽂有关⽂法都是0型⽂法。