编译原理231-3_4-文法直观概念-形式定义.ppt

《编译原理231-3_4-文法直观概念-形式定义.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2.3程序语言的语法描述2.3.1上下文无关文法2.3.2语法分析树与二义性2.3.3形式语言鸟瞰2.3.1上下文无关文法一、文法引入二、符号和符号串三、文法的直观概念四、文法和语言的形式定义三、文法的直观概念采用EBNF来表示英语中一种句子的构成规则:<句子>∷=<主语><谓语><主语>∷=<冠词>[<形容词〉]<名词><谓语>∷=[<助动词>]<动词><冠词><名词><名词>∷=wolf

2、goat

3、rabbit

4、tiger<冠词>∷=the

5、a

6、an<形容词>∷=gray

7、red<助动词>∷=will<动词>∷=eat

8、like补充例用规则产生句子.(推

9、导)使用一条规则,把左边的部分替换成右边的部分。用规则判别句子的合法性[]：方括号表示其内的成分为任选项判断一个符号串是否为语法上正确的<句子>运用规则,把左边的部分替换成右边的部分,如果可以推导出(产生)该符号串,则该符号串是正确的句子可以图示化表示这种推导,得到语法分析树参考p27做练习:画出"Thegraywolfwilleatthegoat."的语法树有关文法概念的给出<句子>∷=<主语><谓语><主语>∷=<冠词>[<形容词〉]<名词><名词>∷=wolf

10、goat

11、rabbit

12、tiger产生式产生式产生式非终结符<>终结符开始符号(识别符号

13、)文法G:一组非终结符,一组终结符,一个开始符号,一组产生式终结符终结符是组成语言的基本符号,不可再分割，不能由其它文法符号定义词法规则终结符是字母,数字,其他合法符号语法规则从语法分析的角度,终结符指单词符号,基本字,标识符,常数,算符,界符等非终结符非终结符:语法成分,语法短语，语法单位，语法变量，语法范畴，语法实体非终结符可由其它文法符号定义。不是用户自己写的非终结符给语言强加了一种层次结构每个非终结符表示一定符号串的集合开始符号(识别符号)开始符号是我们最终感兴趣的语法范畴是文法最终要定义的语法结构四、文法和语言的形式定义产生式(规则)文法直接推导,

14、直接归约推导,归约句型,句子语言文法等价(补充)最左推导,最右推导1.文法(a)文法的形式定义:G=(VT，VN，P，S)VN∩VT=φV:文法符号的集合(文法G的字母表)V=VN∪VT(补充)语言LVT*终结符号集合非终结符号集合产生式集合开始符号2.产生式重写规则、产生式、生成式aproductionrule、arewritingrule有序对(α，β)α→β(书上A→α)α∷=βα：规则的左部α∈V+β：规则的右部β∈V*产生式可以递归产生式左部的符号可以在右部出现.例:表达式的定义E→iE→E+EE→E*EE→(E)p28(b)文法举例文法G=(V

15、N，VT，P，S)，VN={S}，VT={0，1}，P={S→0S1，S→01}补充例文法1补充例文法2文法G=(VN，VT，P，S)，VN={标识符，字母，数字}，VT={a,b,c,…，x,y,z,0,1,…，9}P={〈标识符〉→〈字母〉〈标识符〉→〈标识符〉〈字母〉〈标识符〉→〈标识符〉〈数字〉〈字母〉→a〈字母〉→b…〈字母〉→z〈数字〉→0〈数字〉→1…〈数字〉→9}S=〈标识符〉(c)文法的写法VN–A,B,C…,<表达式>,<程序>VT–a,b,c,…,1,2,3,…V–,,…G=({S,A}，{a,b}，P，S)，P＝{S→aAb

16、，A→ab，A→aAb，A→ε}补充:文法的写法1VNVTG=({S,A}，{a,b}，P，S)，P：S→aAb，A→ab，A→aAb，A→ε补充:文法的写法2G：S→aAb，A→ab，A→aAb，A→εG[S]：A→ab，A→aAb，A→ε，S→aAb补充:文法的写法3开始符号:第一条产生式的左部开始符号A→α1，A→α2，…A→αn缩写为：A→α1

17、α2

18、…

19、αnG[S]：A→ab

20、aAb

21、ε，S→aAb补充:文法的写法4候选式思考题文法的形式定义对编译器有何作用?如何用文法阐明语言的语法?一个上下文无关文法如何定义语言?29举例G:E→E+E

22、E*E

23、

24、(E)

25、iEE+EE+ii+i从E到i+i的一个推导证明i+i是上述文法定义的一个表达式3.直接推导,直接归约文法G=(VT，VN，P，S)α→β是一产生式,v=γαδ，w=γβδ即:vww是v的直接推导，v直接推出w,w直接归约到vγαδγβδ补充定义αAβ直接推出αγβ即:αAβαγβ,仅当A→γ是一个产生式,且α,β∈V*书上定义p29思考题αα是否正确?直接推导举例G1:S→0S1S→01G2:〈标识符〉→〈字母〉〈标识符〉→〈标识符〉〈字母〉〈标识符〉→〈标识符〉〈数字〉〈字母〉→a

26、b

27、…

28、z

29、A

30、B

31、…

32、Z〈数字〉→0

33、1

34、…

35、

36、94.推导出,归约到序列α1α2…αn称为α1