|
知识路径: > 计算机系统基础知识 > 计算机软件基础知识 > 程序设计语言和语言处理程序知识 > 汇编、编译、解释系统的基本知识和基本工作原理 > 程序语言翻译基础 > 编译程序基本原理 > 语法分析 >
|
相关知识点:3个
|
|
|
|
上下文无关文法属于乔姆斯基定义的2型文法,被广泛地用于表示各种程序设计语言的语法。对于上下文无关文法G[S]=(VN,VT,P,S),其产生式的形式都是A→β,其中A∈VN,β∈(VN∪VT)*。
|
|
|
若不加特别说明,下面用大写英文字母A、B、C等表示非终结符,小写英文字母a、b、c等表示终结符号,u、v、w等表示终结符号串,小写希腊字母α、β、γ、δ等表示终结符和非终结符构成的文法符号串。由于一个上下文无关文法的核心部分是其产生式集合,所以文法可以简写为其产生式集合的描述形式。
|
|
|
(1)规范推导(最右推导)。如果在推导的任何一步其中α、β是句型),都是对α中最右边的非终结符进行替换,则称这种推导为最右推导。最右推导常称为规范推导。同理可定义最左推导。
|
|
|
(2)短语、直接短语和句柄。设αδβ是文法G的一个句型,即,且满足和,则称δ是句型αδβ相对于非终结符A的短语。特别地,如果有,则称δ是句型αδβ相对于产生式A→δ的直接短语。一个句型的最左直接短语称为该句型的句柄。
|
|
|