ML-Yacc入门

ML-Yacc是Yacc的ML语言实现。

yacc(Yet Another Compiler Compiler),是Unix/Linux上一个用来生成编译器的编译器(编译器代码生成器)。yacc生成的编译器主要是用C语言写成的语法解析器(Parser),需要与词法解析器Lex一起使用,再把两部份产生出来的C程序一并编译。yacc本来只在Unix系统上才有,但现时已普遍移植往Windows及其他平台。

yacc的输入是巴科斯范式(BNF)表达的语法规则以及语法规约的处理代码,Yacc输出的是基于表驱动的编译器,包含输入的语法规约的处理代码部分。

yacc是开发编译器的一个有用的工具,采用LALR(1)语法分析方法。

yacc最初由AT&T的Steven C. Johnson为Unix操作系统开发,后来一些兼容的程序如Berkeley Yacc,GNU bison,MKS yacc和Abraxas yacc陆续出现。它们都在原先基础上做了少许改进或者增加,但是基本概念是相同的。

由于所产生的解析器需要词法分析器配合,因此Yacc经常和词法分析器的产生器——一般就是Lex——联合使用。IEEE POSIX P1003.2 标准定义了Lex和Yacc的功能和需求。

ML-Yacc要求使用如下的基本格式:

{user declarations}
%%
{ML-Yacc declarations}
%%
{rules}

类似于ML-Lex,{user declarations}用户声明部分用于定义规则中用到的自定义值。建议尽量缩短这部分的代码。

{ML-Yacc declarations}部分用于进行必须和可选的声明。如,必须声明终结符、非终结符以及与他们相关联的值类型,必须定义语法分析器的名字,position值的类型,可以跟在开始符号后面的终结符和非终结符有哪些等。可以选择的声明有:终结符的优先级,禁止默认的规约,规定生成程序是否在.desc文件中生存冗长的描述信息等等。

{rules}部分包括上下文无关文法和相应的语义行为。

##必要声明

%name
必须给语法分析器指定一个名字

%term %nonterm
必须定义终结和非终结符集。这些声明类似于ML数据类型定义,语法如下:

%term NAME1 [of ML-type]

      |   NAME2 [of ML-type]

不要使用ML的关键字作为符号名! 否则ML-Yacc将无法编译。确保%term声明中指定类型是完全合法的类型,或者是在加载环境时签名中使用的类型。不要使用任何用户声明部分的类型。

%pos
你必须使用%pos声明位置值的类型,语法如下:

%pos <ML-type>

这里的类型务必和词法分析中的相同,并且不能是多态的。

##可选声明

%arg

%eop

%noshift

%header

%left,%right,%nonassoc

%start

%verbose

##用来加强错误恢复的声明

%keyword

%prefer

%subst

%change

%value