ANTLR

ANTLR是常用的词法分析器生成器，通过编写包含词法规则的g4文件，便可以自动生成一个词法分析器。

一个g4文件主要的词法分析相关的内容是词法规则和句法规则。其中句法规则以小写字母开头，词法规则以大写字母开头。

grammar SimpleExpr;

@header {
package simpleexpr;
}

//*: 0-n
prog : stat* EOF ;

//'if': literal
stat : expr SEMI
     | ID EQUAL expr SEMI
     | IF expr SEMI
     ;

EQUAL : '=' ;

SEMI : ';' ;

IF : 'if' ;

//|: or
//(): subrule
expr : expr (MUL|DIV) expr
     | expr (ADD|SUB) expr
     | ID
     | INT
     ;

SUB : '-' ;

ADD : '+' ;

DIV : '/' ;

MUL : '*' ;

ID : (LETTER|'_') (LETTER|DIGIT|'_')* ;

//+: 1-n
INT : '0'|([1-9][0-9]*) ;

WS : [ \t\r\n]+ -> skip ;

SL_COMMENT : '//' .*? '\n' ->skip;

ML_COMMENT : '/*' .*? '*/' ->skip;

fragment LETTER : [a-zA-Z] ;

fragment DIGIT : [0-9] ;

语言

字母表

字母表$\Sigma$上一个有限的符号集合

串

字母表$\Sigma$上的串($s$)是由$\Sigma$中符号构成的一个有穷序列。其中空串$\epsilon$的长度为0

串上的运算

连接运算：xy为x串和y串前后连接起来

指数运算：$s^0$为空串，$s^n$为n个s连接

语言

语言是给定字母表$\Sigma$上一个任意的可数的串集合

语言运算

• L和M的并：$L\bigcup M={s\mid s\in L \or s\in M}$
• L和M的连接：$LM={st\mid s\in L \and t\in M}$
• L的Kleene闭包：$L^*=\bigcup^{\infin}_{i=0}L^i$
• L的正闭包：$L^*=\bigcup^{\infin}_{i=1}L^i$

正则表达式

给定字母表$\Sigma$，$\Sigma$上的正则表达式由且仅由以下规则定义

• $\epsilon$是正则表达式
• $\forall a\in \Sigma$，$a$是正则表达式
• 如果$r$是正则表达式，则$(r)$是正则表达式
• 如果$r,s$是正则表达式，则$r\mid s,rs,r^*$为正则表达式

运算优先级：$() > * > 连接 > \mid$

每个正则表达式对应一个正则语言$L(r)$

• $L(\epsilon)={\epsilon}$
• $L(a)={a},\forall a \in \Sigma$
• $L((r))=L(r)$
• $L(r\mid s)=L(r)\bigcup L(s)$
• $L(rs)=L(r)L(s)$
• $L(r^)=(L(r))^$