【形式化的方法】是用一整套帶有嚴(yán)格規(guī)定的符號(hào)體系來(lái)描述問(wèn)題的方法敢艰。
[重點(diǎn)介紹如何采用形式化的方法描述程序設(shè)計(jì)語(yǔ)言]
【形式語(yǔ)言】序列的集合稱為形式語(yǔ)言。
[每個(gè)形式語(yǔ)言都是某個(gè)字母表上按某種規(guī)則構(gòu)成的所有符號(hào)串的集合]
[任何一個(gè)字母表上符號(hào)串的集合均可定義為一個(gè)形式語(yǔ)言]
[形式語(yǔ)言是指不考慮語(yǔ)言的具體意義俊抵，即不考慮語(yǔ)義]
[對(duì)形式語(yǔ)言的描述有兩種方法谁不，一種方法是當(dāng)語(yǔ)言為有窮集合時(shí)，用枚舉法來(lái)表示語(yǔ)言]
[當(dāng)語(yǔ)言為無(wú)窮集合時(shí)徽诲，就要用語(yǔ)法來(lái)描述語(yǔ)言了刹帕。 ]
例如A={ a, b, c }
L1={ a, b, c }
L2={ a, aa, ab, ac }
L3={ c, cc }//有窮集合
L={ 0, 1 } { 0, 1 }*
= { 0, 1, 00, 10, 11, 01, 000, 100, …} //無(wú)窮集合
符號(hào)“->”讀作“生成”或“由…組成”
【產(chǎn)生式】是一個(gè)符號(hào)與一個(gè)符號(hào)串的有序?qū)Γˋ,β），寫(xiě)作：A→β
[ 產(chǎn)生式的作用是告訴我們如何用產(chǎn)生式中的符號(hào)串生成語(yǔ)言中的序列]
例如（1）串110是從A→A0 → A10 → 110產(chǎn)生的【倒推生成】
[ 產(chǎn)生式中出現(xiàn)的符號(hào)分為兩類谎替，一類是終結(jié)符號(hào)偷溺，另一類是非終結(jié)符號(hào)。]
[ 非終結(jié)符號(hào)是出現(xiàn)在規(guī)則左部能派生出符號(hào)或符號(hào)串的那些符號(hào)钱贯，即每個(gè)非終結(jié)符號(hào)表示一定符號(hào)串的集合挫掏，用大寫(xiě)字母表示或用尖括號(hào)把非終結(jié)符號(hào)括起來(lái)。例如秩命，上例中的A尉共。]
2【語(yǔ)法】產(chǎn)生式的非空有窮集合褒傅，通常表示成四元組? ??
G={VN,VT, P, S }
VN是產(chǎn)生式中非終結(jié)符號(hào)的集合。
VT是產(chǎn)生式中終結(jié)符號(hào)的集合袄友。
P 是產(chǎn)生式的集合殿托。
A→a1 | a2 | … | an 【縮寫(xiě)形式】
其中每個(gè)ai有時(shí)也稱為是A的一個(gè)候選式。
注：語(yǔ)法是不唯一的
【表達(dá)式E】若 E1和 E2是算術(shù)表達(dá)式, 則E1＋E2剧蚣、E1*E2支竹、(E1) 也是算術(shù)表達(dá)式
【語(yǔ)言的形式推導(dǎo)】推導(dǎo)用“=>”
1、直接推導(dǎo)：推導(dǎo)的依據(jù)是產(chǎn)生式券敌。
S=>0S1——【句型】——含終結(jié)符[句型包括句子]
S=>0011——【句子】——不含終結(jié)符
約定:
第一條規(guī)則的左部是開(kāi)始符號(hào)唾戚。
對(duì)語(yǔ)法G不用四元式顯示表示，僅只將產(chǎn)生式寫(xiě)出待诅。
分為【最左最右推導(dǎo)】最右比最左簡(jiǎn)單
【歸約】
【遞歸產(chǎn)生式】
如果語(yǔ)法中有產(chǎn)生式叹坦，A→A …? ? 稱為左遞歸。
如果語(yǔ)法中有產(chǎn)生式卑雁， A→ … A? 稱為右遞歸募书。
如果語(yǔ)法中有產(chǎn)生式，A→ …A… 稱為遞歸测蹲。
[在語(yǔ)法中使用遞歸莹捡，使得我們能用有限的產(chǎn)生式去定義無(wú)窮集合的語(yǔ)言。]
【推導(dǎo)和語(yǔ)法樹(shù)】
對(duì)句型的推導(dǎo)過(guò)程給出一種圖形表示, 這種表示稱為語(yǔ)法樹(shù)扣甲，也稱推導(dǎo)樹(shù)篮赢。
[作用:語(yǔ)法樹(shù)是用來(lái)描述句型（句子）語(yǔ)法結(jié)構(gòu)的一種輔助工具。]
[一棵語(yǔ)法樹(shù)表示了一個(gè)句型的種種可能的(但未必是所有的)不同推導(dǎo)過(guò)程, 包括最左(最右)推導(dǎo)]
如果一個(gè)語(yǔ)法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)琉挖，則說(shuō)這個(gè)語(yǔ)法是【二義性】的
若一個(gè)語(yǔ)法中存在某個(gè)句子启泣，它有兩個(gè)不同的最左 (最右) 推導(dǎo)，則這個(gè)語(yǔ)法是二義性的示辈。
【語(yǔ)法二義性的消除】
1. 不改變語(yǔ)法中原有的語(yǔ)法產(chǎn)生式, 僅加進(jìn)一些非形式的語(yǔ)法規(guī)定
2. 構(gòu)造一個(gè)等價(jià)的無(wú)二義性語(yǔ)法寥茫。即把排除二義性的產(chǎn)生式合并到原有語(yǔ)法中,改寫(xiě)原有的語(yǔ)法。
將運(yùn)算符的優(yōu)先順序和結(jié)合規(guī)則：*優(yōu)先于＋; ＋矾麻、*左結(jié)合加到原有語(yǔ)法中, 可構(gòu)造出無(wú)二義性語(yǔ)法如纱耻。【難點(diǎn)】
【短語(yǔ)】總是句型的某個(gè)子串险耀，它對(duì)應(yīng)子樹(shù)未端結(jié)點(diǎn)形成的符號(hào)串弄喘。
【直接短語(yǔ)】是某條規(guī)則右部，它對(duì)應(yīng)簡(jiǎn)單子樹(shù)未端結(jié)點(diǎn)形成的符號(hào)串甩牺。
最左邊的直接短語(yǔ)是【句柄】蘑志。
