第06講-語法分析-I

1、12表達式表達式表達式表達式表達式表達式標(biāo)識符標(biāo)識符表達式表達式表達式表達式(initial)標(biāo)識符標(biāo)識符(rate)數(shù)數(shù)(60)*賓語賓語定語定語 賓語賓語形容詞形容詞(優(yōu)秀的優(yōu)秀的)名詞名詞（大工學(xué)子）（大工學(xué)子）initial + rate * 60id + id * num非終結(jié)符非終結(jié)符 終結(jié)符終結(jié)符 語法分析的任務(wù)語法分析的任務(wù)3語法分析語法分析v目標(biāo)目標(biāo) 線性的詞法記號流線性的詞法記號流 = = 語法樹語法樹v實質(zhì)：無結(jié)構(gòu)的數(shù)據(jù)轉(zhuǎn)換為有結(jié)構(gòu)的數(shù)據(jù)實質(zhì)：無結(jié)構(gòu)的數(shù)據(jù)轉(zhuǎn)換為有結(jié)構(gòu)的數(shù)據(jù)v依據(jù)依據(jù) 上下文無關(guān)語法（描述語法規(guī)則）上下文無關(guān)語法（描述語法規(guī)則）4本講綱要本講綱要v語法分析

2、概述語法分析概述v上下文無關(guān)文法上下文無關(guān)文法v語言和文法語言和文法5v主要內(nèi)容主要內(nèi)容6 78*,()NTNAVVVTNVV9同一個符號可以在同一個符號可以在多個產(chǎn)生式中出現(xiàn)多個產(chǎn)生式中出現(xiàn) 101)字母表中前面的小字母表中前面的小寫字母，如寫字母，如a,b,c2)黑體串黑體串,如如id或或while3)數(shù)字?jǐn)?shù)字 0,1,94)標(biāo)點符號，如括號，標(biāo)點符號，如括號，逗號等逗號等5)運算符號，如運算符號，如+,-等等1)字母表中前面的大字母表中前面的大寫字母，如寫字母，如A,B,C2)字母字母S, 通常它表示通常它表示開始符號開始符號3)小寫字母的名字，小寫字母的名字，如如expr和和stmte

3、xprexpr exprexpr opop expr expr exprexpr ( (exprexpr) )expr expr expr expr exprexpr id idop op + + op op * *E E E A E | E A E | ( (E E ) ) | | E | E | ididA A + | + | * *11E E E A E | E A E | ( (E E ) ) | | E | E | ididA A + | + | * *12letter A-Za-zdigit 0-9id letter(letter|digit)*v主要內(nèi)容主要內(nèi)容13推導(dǎo)：是從文法

4、推出文法所描述的語言中 所包含的合法串集合的動作14推導(dǎo)的定義推導(dǎo)的定義直接推導(dǎo)直接推導(dǎo)“”A A 是文法是文法G G的產(chǎn)生式：的產(chǎn)生式： A A 例：例：G G： S0S1S0S1， S01S01 0 0S S1 1 0 00S10S11 1 00 00S S11 11 00000S10S11111 000 000S S111 111 0000000101111111 S S 0S10S115等價的文法等價的文法 161718EEE EE ()EEE ()EEE+EE ()EEE+idEE ()EEE+ididEEE EE ()EEE ()EEE+EE ()EEE+idEE ()EEE+id

5、id文法、推導(dǎo)與分析樹文法、推導(dǎo)與分析樹v表達式文法表達式文法v語法分析的目標(biāo)是：給出一個句子，比如語法分析的目標(biāo)是：給出一個句子，比如id+idid+id* *id id ，怎么判斷該句子是滿足文法所，怎么判斷該句子是滿足文法所描述的語法規(guī)則？描述的語法規(guī)則？ 判斷是不是存在一個推導(dǎo)，使得判斷是不是存在一個推導(dǎo)，使得E E推導(dǎo)出給定推導(dǎo)出給定的句子的句子19文法、推導(dǎo)與分析樹文法、推導(dǎo)與分析樹v推導(dǎo)過程推導(dǎo)過程 E=E+E=id+E=id+EE=E+E=id+E=id+E* *E=id+idE=id+id* *E=id+idE=id+id* *idid20文法、推導(dǎo)與分析樹文法、推導(dǎo)與分析樹

6、v表達式文法表達式文法v語法分析的目標(biāo)是：給出一個句子，比如語法分析的目標(biāo)是：給出一個句子，比如id+idid+id* *id id ，怎么判斷該句子滿足文法所描述，怎么判斷該句子滿足文法所描述的語法規(guī)則？的語法規(guī)則？ 判斷是不是存在一個推導(dǎo)，使得判斷是不是存在一個推導(dǎo)，使得E E推導(dǎo)出給定的推導(dǎo)出給定的句子句子v語法分析器設(shè)計的角度：語法分析器設(shè)計的角度：如何保證文法能推導(dǎo)出所如何保證文法能推導(dǎo)出所有正確的語法表示，并且只能是這些表示。有正確的語法表示，并且只能是這些表示。21v主要內(nèi)容主要內(nèi)容22文法的二義性，是指對于符合文法規(guī)則的同一個句子，存在兩種可能的分析樹23EEE*+EEidid

7、idEEidE*+EEididv表達式文法二義性的產(chǎn)生原因表達式文法二義性的產(chǎn)生原因24消除文法的二義性消除文法的二義性id id * * id id * * (id+id) (id+id) + + id id * * id id + + idid25EEE*+EEidididEEidE*+EEidid消除文法消除文法二義性的二義性的思想思想消除文法的二義性消除文法的二義性id id * * id id * * (id+id) (id+id) + + id id * * id id + + idididid * * idid * * (id+id)(id+id) T T T T * * F F

8、 | | F F 26 消除文法的二義性消除文法的二義性T T T T * * F F | | F F 27FEidTididT*TFF*EE+idFTididT*TFFid * * id * * id 的分析樹的分析樹 id + id * * id 的分析樹的分析樹 思考題思考題v懸空懸空elseelse文法文法28消除文法的二義性消除文法的二義性 29v 30本講綱要本講綱要v語法分析概述語法分析概述v上下文無關(guān)文法上下文無關(guān)文法v語言和文法語言和文法3132( (a a| |b b) )* *ababA A0 0 a a A A0 0 | | b Ab A0 0 | | a a A A1

9、 1A A1 1 b b A A2 2A A2 2 3312開始開始a0abbv 34A0 a A0 | b A0 | a A1A1 b A2A2 12開始開始a0abb 35 363.23.2 語言和文法語言和文法v能否把詞法分析并入到語法分析中，直接能否把詞法分析并入到語法分析中，直接從字符流進行語法分析從字符流進行語法分析 若把詞法分析和語法分析合在一起，則必須將若把詞法分析和語法分析合在一起，則必須將語言的注解和空白的規(guī)則反映在文法中，文法語言的注解和空白的規(guī)則反映在文法中，文法將大大復(fù)雜將大大復(fù)雜 注解和空白由自己來處理的分析器，比注解和注解和空白由自己來處理的分析器，比注解和空格已由詞法分析器刪除的分析器要復(fù)雜得多空格已由詞法分析器刪除的分析器要復(fù)雜得多37文法、推導(dǎo)與分析樹文法、推導(dǎo)與分析樹v表達式文法表達式文法v語法分析的目標(biāo)是：給出一個句子，比如語法分析的目標(biāo)是：給出一個句子，比如id+idid+id* *id id ，怎么判斷該句子滿足文法所描述的語，怎么判斷該句子滿足文法所描