.B2 :-
正如看到的,这里用正则表达式定义整数。
语法通常用 CB 格式定义,我们的语言可以定义为:
%(=)%!)()
%!)(D0/2 E.B2
)DB-93E%(
如果一个语言的文法是上下文无关的,则它可以用正则解析器来解析。对上下文无关文法
的一个直观的定义是,该文法可以用 CB 来完整的表达。可查看 #))%55
(%'!55"())F!!。
解析器类型Types of parsers
有两种基本的解析器——自顶向下解析及自底向上解析。比较直观的解释是,自顶向下解
析,查看语法的最高层结构并试着匹配其中一个;自底向上解析则从输入开始,逐步将其
转换为语法规则,从底层规则开始直到匹配高层规则。
来看一下这两种解析器如何解析上面的例子:
自顶向下解析器从最高层规则开始——它先识别出“+G,将其视为一个表达式,然后识
别出”+-G为一个表达式(识别表达式的过程中匹配了其他规则,但出发点是最高层
规则)。
自底向上解析会扫描输入直到匹配了一条规则,然后用该规则取代匹配的输入,直到解析
完所有输入。部分匹配的表达式被放置在解析堆栈中。
Stack Input
HI
) HI
)%!)( I
%(
%(
%!)(
%(
自底向上解析器称为 #)'*解析器,因为输入向右移动(想象一个指针首先指向输
入开始处,并向右移动),并逐渐简化为语法规则。
自动化解析Generating parsers automatically
解析器生成器这个工具可以自动生成解析器,只需要指定语言的文法——词汇表及语法规
则,它就可以生成一个解析器。创建一个解析器需要对解析有深入的理解,而且手动的创
建一个由较好性能的解析器并不容易,所以解析生成器很有用。&) 使用两个知名的
解析生成器——用于创建语法分析器的 及创建解析器的 C((你可能接触过 /
和 J!)。 的输入是一个包含了符号定义的正则表达式,C( 的输入是用 CB 格
式表示的语法规则。
HTML 解析器HTML Parser
-./ 解析器的工作是将 #) 标识解析为解析树。
HTML 文法定义The HTML grammar de'nition
&" 组织制定规范定义了 -./ 的词汇表和语法。
非上下文无关文法Not a context free grammar
正如在解析简介中提到的,上下文无关文法的语法可以用类似 CB 的格式来定义。