一个EBNF语法实例
上面的例子用EBNF可以写成: S := '-'? D+ ('.' D+)?
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
提示:EBNF在定义语言方面并不比BNF更强大,只是更方便。凡是用EBNF写的东西都可以转换成BNF的形式。
BNF和EBNF的使用
一般用法
多数编程语言标准都使用一些EBNF变量来定义语言的语法。这有两个好处:一是在语言的语法上没有争议,而是易于编译器的编写,因为编译器的解析器可以用类似YACC这样的“编译器编译器”自动产生。
EBNF也用于许多其他标准,如定义协议格式,数据格式和XML,SGML这样的标记语言。(HTML没有按照语法定义,而是用SGML DTD这样的高级语法定义的。) 在BNF web club
(http://cuiwww.unige.ch/db-research/Enseignement/analyseinfo/BNFweb.html)上可以查到BNF的一个语法集。
如何使用形式语法
现在,我们已经了解什么是BNF和EBNF以及它们的用途了,但还不知道为什么它们很有用以及如何利用它们。
形式语法最明显的用法已经提到过了:一旦为语言制定了形式语法,就完全定义了这个语言。对于那些东西可以用于语言,那些东西不可以就不会有歧义了。这非常有用因为用普通语言描述的语法不仅冗长,而且会产生对不同的解释。 另一个好处是:形式语法是数学产物,可以被计算机理解。实际上有许多程序可以用(E)BNF语法输入,并自动为给定语法的解析器提供处理代码。实际上,这是设计编译器的常见做法:用带有语法输入的所谓“编译器编译器”产生编程语言的解析器代码。
当然,编译器除了做语法检查之外还做许多其他检查,他们也产生代码。这些都没有在(E)BNF中描述,因此编译器编译器通常有针对一种语法中不同代码的代码块连接(也叫做操作)的特殊语法。
最有名的编译器编译器是YACC(Yet Another Complier Complier),产生C代码,其他的编译器还有针对C++,JAVA,Python等等其他语言的。
解析
最简单的方法 自上而下的解析(LL)
按照现有语法解析代码的最简单方法是叫做LL解析(自上而下解析)。它是这样工作的:对每一段代码找出代码开始的非终端标记(叫做初始集)。 然后,在解析时只需要从起始符开始比较不同代码段(符号)初始集和第一
个输入的符号,判断代码段用的是哪个起始符作为开始的(用到了那些符号)。只有不存在一个符号的两个初始集含有相同的终止符时才可以这样。否则,就不能通过输入的第一个终止符选择哪个开始符(符号)了。
LL语法通常按数字分类,比如LL(1), LL(0)等等。括号中的数字是在语法中的任何一点选择适当符号时需要同时考虑的最大终端数。因此 LL(0)根本不需要检查终端(终止符),总能够选择适当的终止符。这种情况只发生在所有符号只有一个替换符的情形,而如果只有一个替换符意味着语言只有一个字符串。也就是说LL(0)没有意义。
最常有也是做有用的LL语法是联络LL(1),通过检查输入的第一个终止符总能够选择适当的替换符。而LL(2)需要检查两个符号,以此类推。
一个LL分析实例
为了说明,我们就实例语法做一个初始集分析。对符号D这非常容易:所有的替换符号跟它们的初始集(它们产生的)一样是一个数字,D符号把由10个数字组成的集合作为初始集。这意味着至少有一个LL(1)语法,因为这时我们需要一个终端来选择适当的替换符。
对DL就会有些麻烦。两个替换符都以D开头,因此都有相同的初始机。这意味着不能够通过检查输入的第一个终止符来选择适当的替换符。但我们可以通过欺骗轻松地克服这个困难:如果输入的第二个终止符不是数字,我们就用第一个替换符,如果两个都是数字,就用第二个替换符。也就是说,这至少是LL(2)语法。
这里其实把事情简化了。DL的替换符并没有告诉我们D @的替换符中的第
一个终止符后哪个终止符是被允许的,因为我们需要知道在DL后面哪个终止符被允许。这个终止符集叫做符号的后续集(follow set of the symbol),这里是“.”,是输入的结尾。
FN符号更糟糕,因为两个替换符都是以数字作为其初始集。检查第二个也终止符没有用,因为在数字列表(DL)中的最后一个数字的后面需要查看第一个终止符,而我们需要读取所有的数字后才能知道有多少数字。由于有多少数字并无限制,这就不是一个对于任意k的LL(k)语法。
或许有些奇怪,S符号很简单。第一个替换项“-”是它的初始集,第二个全部是数字。也就是说,解析时从S符号开始查看输入项来决定使用哪个替换项。如果第一个终端是“-”,就用第一个替换项“-”;否则就用第二个。只有FN和DL替换想会引起麻烦。
一个LL转换实例
其实也没有必要失望。多数非LL(k)语法可以容易地转换成了LL(1)语法。这样我们需要转换两个符号:FN和DL。
FN的问题是两个替换项都以DL开头,但第二个后接一个“.”和另外一个初始DL后面的DL。这很好解决:我们把FN变成只有以一个DL开头的替换项后跟一个FP(分数部分),FP可以是空或是”.”后跟一个DL。变成下面这样: FN := DL FP FP := @ | '.' DL
现在FN没有问题了,因为只有一个替换项,FP也没有问题,因为两个替换项有不同的初设集。分别是输入的结尾和“.”。
DL是块硬骨头,因为主要问题出在递归,而且是复合的,需要从DL中得到一个D。解决方案是给DL一个单独的替换项,一个D后接一个DR(其余的数字)。这时DR就有两个替换项:D和DR或@。第一个替换项以所有的数字为初始集,第二个含有“.”和输入的结尾作为其初始集,从而解决问题。 这样就彻底转换成LL(1)语法了: S := '-' FN | FN FN := DL FP FP := @ | '.' DL DL := D DR DR := D DR | @
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
稍难的方法 自底而上的解析(LR)
一个稍难的方法是移动替换法或叫自底而上解析。这个技术采集所有输入直道发现能够还原成符号的输入。这听起来好像很困难,所以需要给个例子加以说明。我们解析“3.14”看看如何从该语法中产生。我们从读取输入“3”开始: 3
然后,我们查看能否还原成产生它的符号。实际上我们能,它是从符号D产生的,我们用D替换3。这时我们注意到D可以从DL产生,所以用DL替换D。(这个语法有不确定性,我们可以一直还原到FN,但是是错误的。简单起见我们这里跳过错误的步骤,但清晰的语法将不会允许这样的错误发生),之后