跟语法搏斗……

以前一直听别人说写语法是件极其烧脑细胞的事，但是以前没自己写过没什么实感。这回可是好好体会了一次。

因为自顶而下的递归下降parser比较符合人的思维顺序，而相对来说LR系的shift-reduce冲突可能很难找到根源，所以这次在写语法的时候用ANTLR来帮忙了。具体来说是靠ANTLRWorks的编辑器/解释器/调试器来帮忙写出一个能正确解析我想使用的语法构造的LL(*)语法，然后再从这个语法出发来写比较正式的语法，大概还是会回归LALR(1)吧。我还是很想用Irony的。

问题是在不熟悉ANTLR的情况下，即便是递归下降也一样RP多多。我已经试了数不清多少次瞪着解释器里出现的那NoViableAltException发呆了。而且真的出现NoViableAltException，或者别的RecognitionException时，在ANTLRWorks能看到的信息还是觉得太少了。
可能是我现在还不太熟悉ANTLRWorks里的调试器的用法，总觉得真的要出错的时候，就在关键的那一步，一按step就出来一堆decision然后就error了，脑子完全没跟上啊。

结果还是靠把lexer和parser生成出来之后扔到Eclipse里慢慢调试才明白发生了什么事。不过想来也是，假如这时面对的是LR系的parser的话恐怕更郁闷了。
在调试的时候，基本上就是从自己的parser类跳到CommonTokenStream.LA(int)里，继续跳入CommonTokenStream.LT(int)，CommonTokenStream.fillBuffer()，这里会跳入自己的lexer里的nextToken()。我碰到的好几个问题都是在lexer里出现的，刚开始跟是在CommonTokenStream.fillBuffer()里跟，等那个while循环慢慢把token吃进来然后在tokens这个ArrayList里看每个token的type看看对不对。实际上直接在自己的lexer里设断点也应该能行吧。

嘛，我是太不熟悉这玩意了。出现左递归还好办，但很多错误在ANTLRWorks的grammar check里都不会说出来；它也不知道你是不是故意那样写的嘛。我一开始肯定是昏了，居然没想起一个lexeme只能对应于一个token type。然后满怀希望要让"="既属于EQ又属于AssignmentOperator。傻了嗯。

ANTLR会为在语法规则里出现的所有字面量生成匿名的token type，看上去就像T10、T32之类的。为了让生成的代码好读一点，也应该用赋予了名字的词法规则来指定那些字面量，像是左括号"("，右括号")"之类。当希望某个lexeme本身就以一个独立的token type出现而不与其它lexeme混在一起（例如说"="与"+="要有不同的token type）时，这个词法规则就不能有fragment修饰符。

昨晚开始从头琢磨了一个语法出来。现在还相当的初步和粗糙，大概还有不少bug吧，只是我暂时还没看到。能接受这样的输入：

var globalVar : int = 0;

// a line of comment

function globalFunction() {
    function nestedFunction() {
        /* make a local variable */
        var localVar = ( globalVar = 1 );
    }
    nestedFunction(); // call the nested function
}

globalFunction(); // call the global function

生成这样的语法树：


慢慢再拿这东西继续实验吧。我觉得这个语法文件的命就是要被弄得很乱，呵呵。

话说我对C-like的语言彻底改观了。以前没有自己从头写过语法没有体会，这纯C的语法也是一点都不简单啊。像是for循环的初始化和更新的部分，里面到底应该怎么写才对我现在都还不清楚；下面的语法文件里对forStatement写的很明显是猜的+凑的。Java Language Specification 3rd与D 2.0里的定义就很不一样，但这中间的差异可能一直会影响到表达式和语句最基本的规则的写法。到底怎么样比较好，我还是自己慢慢实验慢慢体会吧～

Dolphin.g (2008-03-26 rev 3):

grammar Dolphin;

// Parser

program	:	sourceElements EOF
	;

sourceElements
	:	( sourceElement )+
	;

sourceElement
	:	statement
	|	functionDeclaration
	;

functionDeclaration
	:	FUNCTION Identifier LPAREN formalParameters RPAREN block
	;

formalParameters
	:	formalParameterList
	|	/* empty */
	;

formalParameterList
	:	parameter ( COMMA parameter)*
	;

parameter
	:	Identifier ( COLON TypeSpecifier )?
	;

block
	:	LBRACE sourceElements RBRACE
	;

statement
	:	block
	|	variableStatement
	|	expressionStatement
	|	selectionStatement
	|	iterationStatement
	|	breakStatement
	|	continueStatement
	|	returnStatement
	|	emptyStatement
	;

variableStatement
	:	VAR variableDeclarationList SEMICOLON
	;

variableDeclarationList
	:	variableDeclaration ( COMMA variableDeclaration )*
	;

variableDeclaration
	:	Identifier ( COLON TypeSpecifier )? ( initialiser )?
	;

initialiser
	:	AssignmentOperator expression
	;

selectionStatement
	:	ifStatement
//	|	switchStatement
	;

ifStatement
	:	IF LPAREN expression RPAREN statement
	;

//switchStatement
//	:	
//	;

iterationStatement
	:	doWhileStatement
	|	whileStatement
	|	forStatement
	;

doWhileStatement
	:	DO statement WHILE LPAREN expression RPAREN SEMICOLON
	;

whileStatement
	:	WHILE LPAREN expression RPAREN statement
	;

forStatement
	:	FOR LPAREN ( VAR variableDeclaration | statementExpressionList )? SEMICOLON expression? SEMICOLON statementExpressionList? RPAREN statement
	;

breakStatement
	:	BREAK SEMICOLON
	;

continueStatement
	:	CONTINUE SEMICOLON
	;

returnStatement
	:	RETURN expression? SEMICOLON
	;

emptyStatement
	:	/* empty */ SEMICOLON
	;

expressionStatement
	:	expression SEMICOLON
	;

statementExpressionList
	:	statementExpression ( COMMA statementExpression )*
	;

statementExpression
	:	expression // TODO: this rule requires further refactoring
	;

expression
	:	assignmentExpression
	|	simpleExpression
	;

assignmentExpression
	:	Identifier ( AssignmentOperator | AssignmentShorthandOperator ) expression
	;

simpleExpression
	:	additiveExpression ( RelationalOperator additiveExpression )?
	;

additiveExpression
	:	multiplicativeExpression ( AddOperator multiplicativeExpression )*
	;

multiplicativeExpression
	:	primaryExpression ( MulOperator primaryExpression )*
	;

primaryExpression
	:	LPAREN expression RPAREN
	|	functionInvocationExpression
	|	Identifier // variable
	|	literal
	;

functionInvocationExpression
	:	Identifier LPAREN argumentList RPAREN
	;

argumentList
	:	expression ( COMMA expression )*
	|	/* empty */
	;

literal	:	integerLiteral
	|	FloatingPointLiteral
	|	CharacterLiteral
	|	StringLiteral
	|	BooleanLiteral
	|	NullLiteral
	;

integerLiteral
	:	HexLiteral
	|	OctalLiteral
	|	DecimalLiteral
	;

// Lexer

AssignmentShorthandOperator
	:	( '+=' | '-=' | '*=' | '/=' | '%=' )
	;

RelationalOperator
	:	( '<' | '>' | '==' | '<=' | '>=' | '!=' )
	;

AddOperator
	:	( '+' | '-' )
	;

MulOperator
	:	( '*' | '/' | '%' )
	;

AssignmentOperator
	:	'='
	;

COMMA	:	','
	;

COLON	:	':'
	;

SEMICOLON
	:	';'
	;

LPAREN	:	'('
	;

RPAREN	:	')'
	;

LBRACE	:	'{'
	;

RBRACE	:	'}'
	;

BREAK	:	'break'
	;

CONTINUE:	'continue'
	;

DO	:	'do'
	;

FOR	:	'for'
	;

FUNCTION:	'function'
	;

IF	:	'if'
	;

RETURN	:	'return'
	;

VAR	:	'var'
	;

WHILE	:	'while'
	;

HexLiteral
	:	'0' ('x'|'X') HexDigit+ IntegerTypeSuffix?
	;

DecimalLiteral
	:	('0' | '1'..'9' '0'..'9'*) IntegerTypeSuffix?
	;

OctalLiteral
	:	'0' ('0'..'7')+ IntegerTypeSuffix?
	;

fragment
HexDigit:	('0'..'9'|'a'..'f'|'A'..'F')
	;

fragment
IntegerTypeSuffix
	:	('l'|'L')
	;

FloatingPointLiteral
	:	('0'..'9')+ '.' ('0'..'9')* Exponent? FloatTypeSuffix?
	|	'.' ('0'..'9')+ Exponent? FloatTypeSuffix?
	|	('0'..'9')+ Exponent FloatTypeSuffix?
	;

fragment
Exponent:	('e'|'E') ('+'|'-')? ('0'..'9')+
	;

fragment
FloatTypeSuffix
	:	( 'f' | 'F' | 'd' | 'D' )
	;

BooleanLiteral
	:	'true'
	|	'false'
	;

NullLiteral
	:	'null'
	;

CharacterLiteral
	:	'\'' ( EscapeSequence | ~( '\'' | '\\' ) ) '\''
	;

StringLiteral
	:	'"' ( EscapeSequence | ~( '\\' | '"' ) )* '"'
	;

fragment
EscapeSequence
	:	'\\' ( 'b' | 't' | 'n' | 'f' | 'r' | '\"' | '\'' | '\\' )
	|	UnicodeEscape
	|	OctalEscape
	;

fragment
OctalEscape
	:	'\\' ( '0'..'3' ) ( '0'..'7' ) ( '0'..'7' )
	|	'\\' ( '0'..'7' ) ( '0'..'7' )
	|	'\\' ( '0'..'7' )
	;

fragment
UnicodeEscape
	:	'\\' 'u' HexDigit HexDigit HexDigit HexDigit
	;

TypeSpecifier
	:	'boolean'
	|	'char'
	|	'short'
	|	'int'
	|	'long'
	|	'double'
	|	'string'
	;

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

WS	:	( ' ' | '\t' | '\r' | '\n' )+ { $channel = HIDDEN; }
	;

Comment
	:	'/*' ( options { greedy = false; } : . )* '*/' { $channel = HIDDEN; }
	;

LineComment
	:	'//' ~('\n'|'\r')* '\r'? '\n' { $channel = HIDDEN; }
	;

评论

3 楼 lwwin 2008-03-28  

偶不习惯OO那种繁琐的东西，偶大概能够看懂的也只有C了罢－ －！

2 楼 RednaxelaFX 2008-03-28  

lwwin 写道

貌似是比较新的C实现？

没啦。基本上是想从简单的东西做起来找感觉。
这东西从C与ECMAScript 4糅合简化而来的。暂时定义了一些primitive type，以ECMAScript 4/ActionScript 3的形式给变量标注类型（可选标注），然后允许嵌套的函数定义这样。没有面向对象的支持。要把canconial name的问题都考虑上的话好麻烦 T T
总之这个慢慢来……

1 楼 lwwin 2008-03-28  

貌似是比较新的C实现？
支持随机定义貌似-v-+ 好长好长

最近电源坏了－ －