人工智能_编译new第三章上下文无关文法.ppt
《人工智能_编译new第三章上下文无关文法.ppt》由会员分享,可在线阅读,更多相关《人工智能_编译new第三章上下文无关文法.ppt(29页珍藏版)》请在启牛文库网上搜索。
1、程序语言的语法描述与分析,目的:,语言的语法结构的形式描述从形式描述中,研究语法分析器的构造(算符优先分析法和递归子程序分析法),本章内容引言-文法文法与语言-上下文无关文法-推导与语言语法树与二义性,第三章 上下文无关文法(context-free grammar),文法(grammar),问题:如何描述语言定义:文法是描述语言的语法结构的形式规则(即语法规则)目的:解决语言的有穷说明问题,包含对语法的描述,但却不表达任何语义,一、引言,1、文法的描述应达到要求:2、文法分类:分为四类(0、1、2、3型文法),对应四类语言;与程序语言语法有关的是上下文无关文法,形式上严格、准确;易于理解;具
2、有较强的描述能力;有利于句子的分析和翻译,构造语法分析器,3、上下文无关文法的特点:它所定义的语法范畴(或语法单位)是完全独立于这种范畴可能出现的环境的,说明,上下文无关文法只能描述一部分语言,但已足够 描述现今的程序设计语言自然语言要用其他的文法来描述,二、文法与语言,1、一个上下文无关文法G是一个四元式(VT,VN,S,P),其中:,例1、考虑下面的算术表达式的文法及语言,VT:id+*/()VN:表达式、运算符S:表达式P:表达式-表达式 运算符 表达式表达式-(表达式)表达式-表达式表达式-id运算符-+|*|/|,得到 文法G1(E):,E-EAE|(E)|E|idA-+|*|/|,
3、该文法的:VN是出现P的左部所有符号集合V是P的所有符号VT=V VNS是该文法所定义的句子名字写出了P,就能找出其它三元素,由此可见,文法G1(E)所定义的语言是上述算术表达式,如:id+id,id*(id+id)等它表达了简单算术表达式由id用A连接起来,2、从此可见,终结符:是用以组成语言中的串的基本符号,与程序语言中“单词”是同义语;如:表达式id+(id)*(-id)中,+、*、/、id均为终结符,非终结符:是标记某种串的集合的特定符号,与“语法变量”、“语法范畴”是同义词;如:表达式、运算符都表示一个串的集合,该语法范畴叫“句子”,在程序语言中叫“程序”语言的句子是由一串VN定义,
4、到最后才是一串VT,开始符号:一个VN,标记感兴趣的语法范畴。其它非终结符用以定义其它的串集,这有助于定义该语言,也有助于为它处理的语言提供一个分层的结构;,产生式:规定由终结符和别的语法范畴组成一个新的语法范畴的办法;结构:非终结符-一串非终结符和终结符如:A-,A-左部符号 右部候选式VN=X1X2Xn,XiV,3、习惯记号,VN:大写字母A、B、C、S等VT:小写字母,09,+、等运算符,标点,分界符,黑体字母串id、ifX、Y、Z:文法符号,或VN或VT一个符号u、v、wz:VT中串、:文法符号串(VTVN)*S:开始符号,第一个产生式中出现-:定义为(元语言符号)|:或(元语言符号)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 编译 new 第三 上下文 无关 文法