第二章 文法和語(yǔ)言
2.1文法
文法是定義或描述語(yǔ)法結(jié)構(gòu)的一組形式規(guī)則晾浴。
（1）文法的形式化定義：
G[S]=(Vn，Vt政己，P愧薛，S)
四元組G（
????非空有限非終結(jié)符集VN,
????非空有限終結(jié)符集VT,
????開始符號(hào)S,
????產(chǎn)生式集合P）
2.2語(yǔ)言
（1）推導(dǎo)與規(guī)約
一步推導(dǎo)叫直接推導(dǎo)晨炕，一步或多步推導(dǎo)叫正推導(dǎo)，零步或多步推導(dǎo)叫星推導(dǎo)毫炉。
最左推導(dǎo)每一步展開最左邊的非終結(jié)符瓮栗，最右推導(dǎo)每一步展開最右邊的非終結(jié)符，最右推導(dǎo)又稱為規(guī)范推導(dǎo)瞄勾。
規(guī)約是推導(dǎo)的逆過程费奸，最左推導(dǎo)的逆過程是最右規(guī)約，最右推導(dǎo)的逆過程是最左規(guī)約丰榴，最左規(guī)約又稱為規(guī)范規(guī)約货邓。
（2）句型、句子和語(yǔ)言
設(shè)有文法G[S]：S——>Ab | C四濒，A——>Aa|换况，C——>c
S推導(dǎo)出的符號(hào)串是文法G的句型。
?例如推導(dǎo)出的Ab是一個(gè)句型盗蟆；
S推導(dǎo)出的只含有終結(jié)符的符號(hào)串是文法G的句子戈二。
例如推導(dǎo)出的c是一個(gè)句子；
文法的語(yǔ)言是文法所有句子的集合喳资，記為L(zhǎng)(G)觉吭。
若兩個(gè)文法定義的語(yǔ)言一樣，則稱這兩個(gè)文法是等價(jià)的仆邓。
2.3語(yǔ)法樹
語(yǔ)法樹是一種描述上下文無關(guān)文法句型推導(dǎo)的直觀工具鲜滩，也稱為推導(dǎo)樹、語(yǔ)法分析樹节值。
給定文法G徙硅，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹。
語(yǔ)法樹的根結(jié)點(diǎn)是開始符號(hào)搞疗。
如果一個(gè)結(jié)點(diǎn)A的直接子孫結(jié)點(diǎn)從左到右依次是aBcd嗓蘑，那么A->aBcd一定是該文法的一個(gè)產(chǎn)生式。
在語(yǔ)法樹生長(zhǎng)的任何時(shí)候，所有葉子結(jié)點(diǎn)從左到右排列起來就是一個(gè)句型桩皿。
一個(gè)文法中豌汇，如果一個(gè)句子能有不止一棵語(yǔ)法樹，那么稱此句子具有二義性泄隔；如果一個(gè)文法含有二義性的句子拒贱，則該文法具有二義性。
2.4句型
例：句型：n=E+T*F+i
（1）短語(yǔ)（非直接子樹）
n相對(duì)于E的短語(yǔ)（E1的子樹）：E2+T3*F3佛嬉；
i是相對(duì)于T1的短語(yǔ)
（2）直接短語(yǔ)（直接子樹）
T*F為句型n相對(duì)于產(chǎn)生式T——>T*E的直接短語(yǔ)柜思；
i為句型n相對(duì)于產(chǎn)生式F——>i的直接短語(yǔ)
（3）句柄
定義：一個(gè)句型的最左直接短語(yǔ)成為此句型的句柄
