赵鸿飞四爷:[转载] ANTLR——语法分析 - 6DAN - 博客园

来源：ANTLR中文网站：http://www.antlr.org.cn

语法分析是编译过程的第二步，在词法分析提供的记号流的基础上，对源代码的结构做总体的分析。无论分析的内容有多大语法分析总是由一个启始规则开始的，最后总是生成一棵语法树。一般情况语法规则是一个文法的主体部分，也是编写文法的难点。本章用几个示例来讲述如何用ANTLR定义语法规则。

4.1语法分析的方法

在ANTLR中语法分析定义的规则名必须以小写字母开始大写如“baseClass”，“subfixSymbol”。如果词法规则与语法规则写在同一个文件时，虽然ANTLR中并没有严格定义规则的先后顺序，但一般情况下语法规则写到词法规则的上面，因为整个文法的启始规则是从语法规则开始的，这样可以从上到下查看整个文法。

ANTLR中语法定义的方法与词法基本相同请看下面一个SQL文法的片段示例:

grammar Test;

sqlStatement : selectStatement | insertStatement | deleteStatement;

selectStatement : SELECT (ALL | DISTINCT)? SelectList FROM tableSource;

SelectList : SelectItem+;

tableSource : TableName | '(' selectStatement ') ';

4.2递归定义

定义文法时通常出现递归的情况，比如上例中tableSource中的子查询就是一个递归定义。在C++，C#，java语言中类名这样的符号是用“.”分隔的多个标识符组成的，如java.IO，System.Web.UI等这种情况需要使用递归的方法来定义，递归有左递归和右递归。

左递归:

qualifiedName : qualifiedName '. ' Identifier;

qualifiedName : Identifier;

Identifier : ('a'.. 'z' | 'A'.. 'Z' | '_') ('a'.. 'z' | 'A'.. 'Z' | '_' | '0'.. '9')*;

右递归:

qualifiedName : Identifier '.' QualifiedName

qualifiedName : Identifier;

Identifier : ('a'.. 'z' | 'A'.. 'Z' | '_') ('a'.. 'z' | 'A'.. 'Z' | '_'| '0'.. '9')*;

不过在ANTLR中不允许左递归定义，ANTLR会提示:“rule is left-recursive”错误。ANTLR中还有别一种定义方法，象类名这样的符号递归定义使用这种方法是最好的方案。原因我们会在后面章节讲述。

qualifiedName : Identifier ('.' Identifier)*;

Identifier : ('a'.. 'z' | 'A'.. 'Z' | '_') ('a'.. 'z' | 'A'.. 'Z' | '_' | '0'.. '9')*;

4.3 java方法的文法示例

下面来看一个定义java方法的文法，些文法是从ANTLR自带的java.g示例中选出的一段:

methodDeclaration :type Identifier

(('(' (variableModifier* type formalParameterDeclsRest?)? ')')

('[' ']')*

('throws' qualifiedNameList)?

( methodBody

| ';'

)) ;

formalParameterDeclsRest :

variableDeclaratorId

(',' (variableModifier* type formalParameterDeclsRest?))?

| '...' variableDeclaratorId

;

type : Identifier (typeArguments)?

('.' Identifier (typeArguments)? )* ('[' ']')*

| primitiveType ('[' ']')*

;

variableModifier : 'final' | annotation ;

formalParameterDeclsRest :

variableDeclaratorId

(',' (variableModifier* type formalParameterDeclsRest?))?

| '...' variableDeclaratorId

;

variableDeclaratorId : Identifier ('[' ']')* ;

Identifier : ('a'..'z' | 'A'..'Z' | '_') ('a'..'z' | 'A'..'Z' | '_' | '0'..'9')*;

typeArguments : '<' typeArgument (',' typeArgument)* '>' ;

typeArgument : type

| '?' (('extends' | 'super') type)? ;

qualifiedNameList :qualifiedName (',' qualifiedName)* ;

qualifiedName :Identifier ('.' Identifier)* ;

methodDeclaration为方法定义的起始规则，后面type Identifier为方法的返回值和方法名，( '('(variableModifier* type formalParameterDeclsRest?)? ')' ) ('['']')*中的variableModifier为参数前的标识符，type为参数的类型formalParameterDeclsRest是对参数其余部分的定义，参数表在“（）”中，后面是“[]”字符，这是数组类型为返回值时需要的，因为数据可以是多维的后是用('[' ']')*来定义。

formalParameterDeclsRest用来定义参数表部分，variableDeclaratorId为参数名，如何有一个以上参数(',' (variableModifier* typeformalParameterDeclsRest?))?部分字义了第二个到第N个参数的规则，这里使用了右递归方法。Java1.5中支持可变参数'...' variableDeclaratorId为可变参数的定义。

另外typeArguments配合Identifier来定义泛型类型，使用“<>”括起来一个类型列表，如List。typeArgument与type形成了递归定义，如Hashtable>。

4.4 | 作用范围

上例中的typeArgument : type | '?' (('extends' | 'super') type)?规则无须写成typeArgument:type | ('?' (('extends' | 'super')type)?)。在同一规则或子规则中“|”使其两侧的内容为并列的选择关系，如果有多个“|”则一起为并列的选择关系，需要改变优先顺序时才使用“（）”。

4.5 SELECT语句文法示例

下面给出一个SQL SELECT语句文法片段的例子。

grammar Select;

statement

: selectStatement (SEMICOLON)?;

selectStatement

: queryExpression (computeClause)? (forClause)? (optionClause)?;

queryExpression

: subQueryExpression (unionOperator subQueryExpression)* (orderByClause)?

;

subQueryExpression

: querySpecification | ‘(‘ queryExpression ‘)’

;

querySpecification

: selectClause (fromClause)? (whereClause)? (groupByClause (havingClause)? )?

;

selectClause

: SELECT (ALL | DISTINCT)? (TOP Integer (PERCENT)?)? selectList

;

whereClause

: WHERE searchCondition

;

orderByClause

: ORDER BY expression (ASC | DESC)? (COMMA expression (ASC | DESC)? )*

;

groupByClause

:GROUP BY (ALL)? expression (COMMA expression)* (WITH (CUBE | ROLLUP) )?

;

havingClause

: HAVING searchCondition

;

SEMICOLON : ';';

我们对SELECT语句都比较熟悉，看一下SELECT语句文法的大体结构。selectStatement规则表示整个SELECT语句体系，queryExpression表示查询语句可能由多个子查询用UNION到一起unionOperator代表UNION或UNIONALL关键字，orderByClause子句出现在SELECT语句的最后，这里subQueryExpression和queryExpression之间形成了递归定义，子查询中还可以有子查询。whereClause子句和havingClause子句后面都是查询过滤表达式后成它们共用searchCondition规则。

4.6 HTML文法示例

下面再看一个HTML文法片段示例:

grammar HTML;

options {language=CSharp; output=AST;}

document : OHTML body CHTML;

body : obody (body_content)* CBODY ;

body_content : body_tag | text;

body_tag : block; // | heading | ADDRESS

text : text_tag;

text_tag : form;// phrase | special | font

block : table;//paragraph | list | preformatted | div | center | blockquote | HR |

table : otable (tr)+ CTABLE;

tr : o_tr (th_or_td)* (C_TR)? ;

th_or_td : o_th_or_td (body_content)* (C_TH_OR_TD )?;

form : oform (form_field | body_content)* CFORM;//

oform : '';

form_field : inputField;// | select | textarea;

inputField : '';

obody : '';

CBODY : '

OHTML : '';

CHTML : '';

otable : '';

CTABLE : '';

o_tr : '';

C_TR : '';

o_th_or_td : ('';

C_TH_OR_TD : '' | '';

CFORM : '';

ATTR : WORD ('=' (WORD ('%')? | ('-')? INT | STRING | HEXNUM))?;

HEXNUM : '#' ('0'..'9' | 'a'..'f')+;

INT : (DIGIT)+;

DIGIT : '0'..'9';

WORD : (LCLETTER | '.' | '/') (LCLETTER | DIGIT | '.')+;

STRING : '"' (~'"')* '"' | '\'' (~'\'')* '\'';

LCLETTER : 'a'..'z';

WS : ( ' ' | '\t' | '\n' | '\r' ) + {Skip();} ;

这个可运行的简化的HTML文法中只支持

4.7 Skip()的效果

在HTML文法示例中的开始标记的定义是用语法规则定义的，而结束是用词法规则定义的ANTLR中规则可以灵活定义不拘一格，结束标记只是固定的字符串定义成词法规则就可以了。而开始标记中要包含属性的定义所以用语法规则来定义。其中有一点要注意的是如果我们把开始标记也定义成词法规则会出现什么情况呢？如下面改变一下HTML文法。

OFORM : ‘’

将