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

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

2、下文無關(guān)文法上下文無關(guān)文法的規(guī)則： P(語法符號)X1X2.Xn 賦值語句變量=表達(dá)式文法G定義為四元組(VT,VN,S,P)VT是有限的終極符集合 VN是有限的非終極符集合S是開始符，SVNP是產(chǎn)生式（規(guī)則）的集合1.3 上下文無關(guā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ī)則，代替左邊的符號，產(chǎn)生右端的符號串。A + :表示A通過一步或多步可推導(dǎo)出A * :表示A通過零

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

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

5、語，句柄是哪個(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 例子短語(T+i)*F+i ，整個(gè)的肯定是短語由E推導(dǎo)出來(T+i)*F 是由T推出來的兩個(gè)i ； （T+i）；T；T+i;簡單短語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)，并用符號lm（rm）表示最左（右）推導(dǎo)。 左（右）句型： 用最左推導(dǎo)方式導(dǎo)出的句型，稱為左句型，而用最右推導(dǎo)方式導(dǎo)出的句型，稱為右句型(規(guī)范句型)。結(jié)論： 每個(gè)句子都有相應(yīng)的最右和最左推導(dǎo)（但對句型此結(jié)論不成立）2. 文法分類0型文法: 也稱為短語文法，其產(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