上下文无关文法.pdf

《上下文无关文法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章上下文无关文法课程内容第1章概论第2章词法分析第3章上下文无关文法第4章语法分析第5章语义分析第6章运行时环境第7章代码生成2016/4/6西北工业大学软件与微电子学院1machunyan第3章上下文无关文法第三章上下文无关文法本章的目的：为语言的语法描述寻求形式工具，要求该工具对程序设计语言给出精确无二义的语法描述。基于语法的形式化描述，语法分析算法见第四章。2016/4/6西北工业大学软件与微电子学院2machunyan第3章上下文无关文法第三章上下文无关文法及分析3.1语言的表示3.2上下文无关文法的形式定义形式工

2、3.3分析树具3.4二义性文法注：P为了解内容，不作考核要求40-61作业2016/4/6西北工业大学软件与微电子学院3machunyan第3章上下文无关文法3.1语言的表示(续)如何描述一种语言(符号串的集合)？如果语言是有穷的(仅包含有穷个句子)可以将句子逐一枚举进行表示。如果语言是无穷的，找出语言的有穷表示生成方式(文法)：语言的每个句子可以用定义的规则构造，例如，正规表达式。识别方式(自动机)：用一个过程模型，输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去

3、，例如，DFA2016/4/6西北工业大学软件与微电子学院4machunyan第3章上下文无关文法3.1语言的表示(续)正规表达式的局限性正规表达式不能用于描述配对或嵌套的结构{(n)n

4、n>1}正规表达式不能用于描述下述重复串{wcw

5、w是a和b形成的任意串}2016/4/6西北工业大学软件与微电子学院5machunyan第3章上下文无关文法3.1语言的表示(续)NoamChomsky研究了自然语言的结构，提出了一种描述语言的数学系统(Chomsky文法)，并以此定义了四类性质不同的文法(0型，1型，2型和3型文法)，称为语言（文法）的C

6、homsky分类。其中2型文法（或上下文无关文法）对程序设计语言是最有用的，它可以作为程序设计语言语法结构描述的标准方式。2016/4/6西北工业大学软件与微电子学院6machunyan第3章上下文无关文法3.1语言的表示(续)Chomsky文法用生成方式(规则)描述语言，语言中的每个句子用严格定义的规则构造。文法示例，简单句子的语法结构表示规则:<句子>→<主语><谓语><主语>→<冠词><形容词><名词><谓词>→<动词><直接宾语><直接宾语>→<冠词><名词>把上述两个字符串中间用一箭头分隔构成的有序对称为产生式。其中，“→”表

7、示“由……组成”,“→”也可以用=，::=，:来代替。2016/4/6西北工业大学软件与微电子学院7machunyan第3章上下文无关文法3.1语言的表示(续)例如：包含加法、减法和乘法的简单整型算术表达式的语法结构可由下面的上下文无关文法(2型文法)给出：exp→expopexpexp→(exp)exp→numberop→+

8、-

9、*2016/4/6西北工业大学软件与微电子学院8machunyan第3章上下文无关文法第三章上下文无关文法及分析3.1语言的表示形式工3.2上下文无关文法的形式定义具3.3分析树3.4二义性文法作业2016/4/6西

10、北工业大学软件与微电子学院9machunyan第3章上下文无关文法3.2上下文无关文法的形式定义1.上下文无关文法(即2型文法)的形式定义2.推导和规约的定义3.句型和句子的定义4.最左和最右推导5.文法定义的语言6.递归产生式和递归文法7.chomsky文法的分类---了解8.文法和语言---了解2016/4/6西北工业大学软件与微电子学院10machunyan第3章上下文无关文法1.上下文无关文法(即2型文法)的形式定义：上下文无关文法G是一个四元组，即G=(V，TV，P，S)：N产生式①终结符（或Token）集合VT的右部②非终结符集合V(与V

11、不相交)NT③产生式或文法规则A→α形成的集合P,其中A∈VN，α∈(VT∪VN)*④开始符号S，其中S∈VN注：终结符和非终结符可以用单个产生式字符表示，也可以用字符串表示。的左部2016/4/6西北工业大学软件与微电子学院11machunyan第3章上下文无关文法文法举例例G=({N},{0，1},1{N→0N,N→1N,N→0,N→1},N）其中:非终结符集合：V={N}N终结符集合：V={0，1}T产生式的集合：P={N→0N，N→1N，N→0，N→1}开始符号为：N2016/4/6西北工业大学软件与微电子学院12machunyan第3章上下文

12、无关文法文法举例通常情况下，文法仅用产生式的集合表示：G[N]:也可写成：1G[N]:N→0N