下载文档原格式
编译原理的⽂法和语⾔总结与梳理梳理⽂法和语⾔的内容，理解与总结。
我们都知道，⼀种语⾔必定他的⽂法去描述，它的完整定义包括语法和语义两个⽅⾯。
语⾔和语法是指⼀组规则，⽤它可以形成和产⽣⼀个合适的程序。
⽬前⼴泛使⽤的是上下⽂⽆关⽂法，也就是⽤上下⽂⽆关⽂法作为程序设计的描述⼯具，⽐如⽤A:=B+C表⽰是⼀个合法的赋值语句，则A:=B+就不是合法的赋值语句。
什么是⽂法？⽂法相当于语⾔学（⼈类语⾔）中的语义分析，即分析⼀个句所表⽰的含义。
它是产⽣中间代码或⽬标代码的依据。
⽤EBNF(EBNF是⼀种称为扩展巴克斯范式的形式描述)表⽰就是：<句⼦> ::= <主语><谓语> <主语> ::= <代词>< 名词> <代词>::= 我 | 你 | 他 <名词>::= 王明 | ⼤学⽣ | ⼯⼈ | 英语 <谓语> ::= <动词><直接宾语> <动词> ::= 是 | 学习 <直接宾语> ::=<代词> |<名词>（1）⽂法的形式化定义： G=(V T , V N , P , S) V T：终结符集合，终结符是⽂法所定义的语⾔的基本符号，有时也称为token。
V N：⾮终结符集合，⾮终结符是⽤来表⽰语法成分的符号，有时也称为"语法变量"，可以推出其它的语法成分P：产⽣式集合S：开始符号（2）符号串运算： 符号串的连接：εx=xε=x； 集合的乘积：AB={xy|x∈A,y∈B}；{ε}A=A{ε}=A； 符号串的幂运算：x=abc,x^2=abcabc; 集合的幂运算正闭包A+与闭包A*：A*={ε}∪A+（3）⽂法分类：（4）语⾔的定义与运算 语⾔：在某⼀确定字母表上的特定符号串的集合。
空集ε，集合{ ε }也是符合此定义的语⾔。
第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[〈表达式〉]是二义的。
名词解释编译：编译程序的翻译过程。
词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成.语言：由文法G生成的语言记为L(G),它是文法G的一切句子的集合:L(G)={x|S =>* x，其中S为文法的开始符号，且x ∈VT*}二义文法：若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。
或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。
二义语言：如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。
属性文法：属性文法(attribute grammar)是一个三元组：A=(G,V,F),其中G:是一个上下文无关文法,V:有穷的属性集,F:关于属性的属性断言或一组属性的计算规则(称为语义规则) 。
活动记录：一个过程的一次执行所需要的信息，使用一个连续的存储区来管理这个区（块），叫做一个活动记录AR。
词法：规定什么是正确的单词，boy 不能写成byo等等。
语法（文法）：是指一组规则，用它可以形成和产生一个合适的程序。
（定义什么样的符号序列是合法的）语义：自然语言中词语的意义，逻辑形式系统中符号的解释。
（定义什么样的符号序列是有含义的）句子：有文法G[s]，若S =>* x，且x∈VT*，则称x是文法G的句子。
句型：有文法G[s]，若S =>* x，则称x是文法G的句型。
语法树：设G=( VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树。
最左/最右推导：在推导的任何一步α β，其中α、β是句型，都是对α中的最左（右）非终结符进行替换。
自上而下分析：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。
自下而上分析：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。
短语：存在文法G[s],S =>* αAδ且 A =>+ β，则称β是句型αβδ相对于非终结符A的短语。
