为了了解自顶向下(自上而下)分析的一般过程和问题我们首先回顾在“文法和语言”一章中介绍的关于句子、句型和语言的定义及什么叫最左推导、最右推导和规范推导的基本概念。在确定的自顶向下语法分析中用的是最左推导。
句型、句子、语言的定义
句型:
有文法G [S], 若S
x,且x∈ V
*
则称x是文法G [S]的句型。
符号
表示经过0步或若干步的推导。
句子:
有文法G[S],若S
x,且x∈V
T
*
,则称x是文法G [S]的句子。
例:G[S]: S→0S1, S→01
可有推导 S
0S1
00S11
000S111
00001111
说明00001111是G[S]的句子。
最左(最右)推导:在推导的任何一步α
β (其中α、β是句型),都是对α中的最左(右)非终结符进行替换。
最右推导被称为规范推导。
由规范推导所得的句型称为规范句型。