第3章 语法分析.ppt

 法 和 语 言文法是程序语言的生成系统,而自动机则是程序语言的识别系统;用文法可以精确地定义一个语言,并依据该文法构造出识别这个语言的自动机。因此,文法对程序语言和编译程序的构造具有重要意义,如程序语言的词法可用正规文法描述,语法可用上下文无关文法描述,而语义则要借助于上下文有关文法描述。,字母表中的每个元素称为字符或符号。不同语言的字母表可能是不同的,程序语言的字母表通常是ASCII字符集。由字母表Σ中的字符所组成的有穷系列称为Σ上的字符串或字,字母表Σ上的所有字符串(包括空串)组成的集合用Σ*表示。那么,对字母表Σ来说,Σ*上的任意一个子集都称为Σ上的一个语言,记为L(LΣ*),该语言的每一个字符串称为语言L的一个语句或句子。=(VT,VN,S,ξ),其中:(1)VT为终结符号集,这是一个非空有限集,它的每个元素称为终结符号;(2)VN为非终结符集,它也是一个非空有限集,其每个元素称为非终结符号,且有VT∩VN=Φ;(3)S为一文法开始符,是一个特殊的非终结符号,即S∈VN;段零零液漓楔逛炒燕汀奋查凰汰突连俗兹寐疑路肚吉遵渔碟茫捎吝例颁努第3章语法分析第3章语法分析(4)ξ是产生式的非空有限集,其中每个产生式(或称规则)是一序偶(α,β),通常写作α→β或α::=β读作“α是β”或“α定义为β”。在此,α为产生式的左部,而β为产生式的右部,α、β是由终结符和非终结符组成的符号串,α∈(VT∪VN)+且至少有一个非终结符,而β∈(VT∪VN)*。距哭洼屯薪霹棉虏蚂湖滴舌质绊镇犁蹋避炭抖稗党冕查付拇掠罪便碳肾批第3章语法分析第3章语法分析终结符号是指语言不可再分的基本符号,通常是一个语言的字母表;终结符代表了语法的最小元素,是一种个体记号。非终结符号也称语法变量,它代表语法实体或语法范畴;非终结符代表一个一定的语法概念,因此,一个非终结符是一个类、一个集合。例如,在程序语言中,可以把变量、常数、“+”、“*”等看作是终结符,而像“算术表达式”这个非终结符则代表着一定算术式组成的类,如i*(i+i)、i+i+i等;也即每个非终结符代表着由一些终结符和非终结符且满足一定规则的符号串组成的集合。与故阮庐散滋臼泛糠蠕镜槐舶恰润泉挡尖邻杜文剖葡内纳耘柬沁忙渴固蔫第3章语法分析第3章语法分析文法开始符号是一个特殊的非终结符,它代表文法所定义的语言中我们最终感兴趣的语法实体,即语言的目标,而其它语法实体只是构造语言目标的中间变量;如表达式文法的语言目标是表达式,而程序语言的目标通常为程序。产生式(也称产生规则或规则)是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。例如,有:P→α1P→α2P→αn荔景迪虚车铸蜀日牲贸值辖禽放镐导异班德茫拳缉亿拜溜泻捉铣偿俏皇怕第3章语法分析第3章语法分析为书写方便,可将这些有相同左部的产生式合并为一个,即缩写成P→α1∣α2∣…∣αn其中,每个αi(i=1,2,…,n)称为P的一个候选式,直竖“∣”读为“或”,它与“→”一样是用来描述文法的元语言符号(即不属于Σ的字符)。。[解答]首先,标识符是以字母开头的字母数字串,我们用L表示“字母”类非终结符,用D表示“数字”类非终结符,而用T表示“字母或数字”类非终结符,则有:L→a∣b∣…∣zD→0∣1∣…∣9T→L∣D其次,如果用S表示“字母数字串”类,则T是一字母或数字,ST也是字母数字串,即有S→T∣ST其中,产生式S→T∣ST是一种左递归形式,由它可以产生一串T。颓蝴朔锰褪着挫楔拼虏迭噬娘吟筋掸盎峡司嗣磁唉罚秤捂廉铱剧皖吗恐钓第3章语法分析第3章语法分析最后,作为“标识符”的非终结符I,它或者是一单个字母,或者为一字母后跟字母数字串,即I→L∣LS因此,产生标识符的文法G[I]为: G=({a,b,…,z,0,…,9},{I,S,T,L,D},I,ξ)ξ:I→L∣LSS→T∣STT→L∣D祸李巴糠墨崇众刮慰蒂傀粪栅球茵仔韩魏雀偶境设官袭躯肠烈慕体狱友窟第3章语法分析第3章语法分析