6.語法分析_形式語言基礎

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

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

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

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

5、語，句柄是哪個？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 ，整個的肯定是短語由E推導出來(T+i)*F 是由T推出來的兩個i ； （T+i）；T；T+i;簡單短語T 兩個i句柄T基本概念(3)設有文法G直接左遞歸：若有EE形式的規(guī)則，則稱E是直接左遞歸。直接右遞歸：若有EE形式的規(guī)則，則稱E是直接右遞歸。左遞歸：若有E+E，則稱E是左遞歸。右遞歸：若

6、有E+E，則稱E是右遞歸。遞歸：若有E+1E2基本概念(3)最左（右）推導： 如果進行推導時選擇的是句型中的最左(右）非終極符，則稱這種推導為最左(右)推導，并用符號lm（rm）表示最左（右）推導。 左（右）句型： 用最左推導方式導出的句型，稱為左句型，而用最右推導方式導出的句型，稱為右句型(規(guī)范句型)。結論： 每個句子都有相應的最右和最左推導（但對句型此結論不成立）2. 文法分類0型文法: 也稱為短語文法，其產(chǎn)生式具有形式: ，其中,(VTVN)*，并且至少含一個非終極符 1型文法: 也稱為上下文相關文法。它是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型文法: 也稱為上下文無關文法。它是1