6.語(yǔ)法分析_形式語(yǔ)言基礎(chǔ)

1、第三章：語(yǔ)法分析 文法與語(yǔ)言文法的分類 文法的相關(guān)概念內(nèi)容介紹文法與語(yǔ)言文法的相關(guān)概念文法的分類1.1 語(yǔ)言與文法文法的產(chǎn)生：自然語(yǔ)言與程序設(shè)計(jì)語(yǔ)言的區(qū)別語(yǔ)言的三個(gè)基本要素：語(yǔ)法、語(yǔ)義、語(yǔ)用1.1 語(yǔ)言與文法文法能清晰地描述程序設(shè)計(jì)語(yǔ)言的語(yǔ)法構(gòu)成易于理解。文法能自動(dòng)地構(gòu)造有效的語(yǔ)法分析器，檢查源程序是否符合語(yǔ)言規(guī)定的語(yǔ)法形式。文法定義可以了解程序設(shè)計(jì)語(yǔ)言的結(jié)構(gòu)，有利于將源程序轉(zhuǎn)化為目標(biāo)代碼，以及檢查出語(yǔ)法錯(cuò)誤?；谖姆▽?shí)現(xiàn)的語(yǔ)言易于擴(kuò)展。1.2 巴克斯范式BNFBNF：語(yǔ)法成分:=組成部分賦值語(yǔ)句:=變量=表達(dá)式變量:=標(biāo)識(shí)符|下標(biāo)變量|指針變量.表達(dá)式:=算術(shù)表達(dá)式|邏輯表達(dá)式. 1.3 上

2、下文無關(guān)文法上下文無關(guān)文法的規(guī)則： P(語(yǔ)法符號(hào))X1X2.Xn 賦值語(yǔ)句變量=表達(dá)式文法G定義為四元組(VT,VN,S,P)VT是有限的終極符集合 VN是有限的非終極符集合S是開始符，SVNP是產(chǎn)生式（規(guī)則）的集合1.3 上下文無關(guān)文法例子和簡(jiǎn)寫：G=VN,VT,P,S VN=N,D VT=0,1,2,.,9 P=ND, NND, D0|1|.|9多條規(guī)則 S=N 基本概念(1)直接推導(dǎo)：如果A是一個(gè)產(chǎn)生式，則有1A212,其中表示一步推導(dǎo)。這時(shí)稱12是由1A2直接推導(dǎo)的。 的含義是，使用一條規(guī)則，代替左邊的符號(hào)，產(chǎn)生右端的符號(hào)串。A + :表示A通過一步或多步可推導(dǎo)出A * :表示A通過零

3、步或多步可推導(dǎo)出 基本概念(1)句型：設(shè)有文法G，如果有S* ，則稱符號(hào)串為G的句型 。我們用SF(G)表示文法G的所有句型的集合 句子：設(shè)為文法G的一個(gè)句型，且只包含終極符，則稱為G的句子 語(yǔ)言：L(G)= u| S +u ,u VT* 。 文法G所定義的語(yǔ)言是其所有句子的集合。1.4 基本概念與高級(jí)語(yǔ)言語(yǔ)法每一種高級(jí)程序設(shè)計(jì)語(yǔ)言都有自己的語(yǔ)法符合高級(jí)語(yǔ)言文法的程序就是該語(yǔ)法的句子所有程序組成的集合就構(gòu)成了語(yǔ)言。1.4 基本概念與高級(jí)語(yǔ)言文法PASCAL語(yǔ)言語(yǔ)法例子：progarm ()var begin.end1.5 驗(yàn)證程序是不是語(yǔ)法的句子最基本的方法：采用類搜索算法，從開始符出發(fā)進(jìn)行推

4、導(dǎo)用剪枝來提高效率兩種基本思想自頂向下的語(yǔ)法分析：從開始符出發(fā)，根據(jù)定義看是否可以推導(dǎo)出程序。自底向上的語(yǔ)法分析：從程序出發(fā)，用規(guī)則的左部替換規(guī)則的右部，一直到規(guī)約成開始符?；靖拍?2)短語(yǔ) 設(shè)S是文法的開始符，有S*1A2，如果有 A + 則稱是句型12的一個(gè)短語(yǔ)。簡(jiǎn)單短語(yǔ) 設(shè)S是文法的開始符，有S*1A2，如果有 A 則稱是句型12的一個(gè)簡(jiǎn)單短語(yǔ)。 句柄 句型中的最左簡(jiǎn)單短語(yǔ)稱為句柄。1.6 例子E E+T| TT T *F| FF ( E ) | i（標(biāo)識(shí)符）這個(gè)文法的開始符就是E，非終極符是E T F終極符就是+ * ( )問：(T+i)*F+i 是不是文法的句型，有哪些短語(yǔ)，簡(jiǎn)單短

5、語(yǔ)，句柄是哪個(gè)？1.6 例子 E E+T T+T T*F+T F*F+T ( E ) * F+T ( E + T ) * F+T ( T + T ) * F + T ( T + F ) * F +T ( T + i ) * F+ T ( T + i ) * F + i 1.6 例子短語(yǔ)(T+i)*F+i ，整個(gè)的肯定是短語(yǔ)由E推導(dǎo)出來(T+i)*F 是由T推出來的兩個(gè)i ； （T+i）；T；T+i;簡(jiǎn)單短語(yǔ)T 兩個(gè)i句柄T基本概念(3)設(shè)有文法G直接左遞歸：若有EE形式的規(guī)則，則稱E是直接左遞歸。直接右遞歸：若有EE形式的規(guī)則，則稱E是直接右遞歸。左遞歸：若有E+E，則稱E是左遞歸。右遞歸：若

6、有E+E，則稱E是右遞歸。遞歸：若有E+1E2基本概念(3)最左（右）推導(dǎo)： 如果進(jìn)行推導(dǎo)時(shí)選擇的是句型中的最左(右）非終極符，則稱這種推導(dǎo)為最左(右)推導(dǎo)，并用符號(hào)lm（rm）表示最左（右）推導(dǎo)。 左（右）句型： 用最左推導(dǎo)方式導(dǎo)出的句型，稱為左句型，而用最右推導(dǎo)方式導(dǎo)出的句型，稱為右句型(規(guī)范句型)。結(jié)論： 每個(gè)句子都有相應(yīng)的最右和最左推導(dǎo)（但對(duì)句型此結(jié)論不成立）2. 文法分類0型文法: 也稱為短語(yǔ)文法，其產(chǎn)生式具有形式: ，其中,(VTVN)*，并且至少含一個(gè)非終極符 1型文法: 也稱為上下文相關(guān)文法。它是0型文法的特例，要求| | (S例外，但S不得出現(xiàn)于產(chǎn)生式右部)。 或者是：A1 A2 anbncn n=1 : S aSBC|aBC CB HB HB HC HC BC aB ab bB bb bC bc cC cca2. 文法的分類2型文法: 也稱為上下文無關(guān)文法。它是1