简单的C语言解释运行器实现（三）—— 定义语法

好的，词法分析就结束了，我们开始语法分析吧。

首先为了简化问题，我们对C语言作出如下限制：
1. 没有switch语句
2. 不支持函数指针
3. 没有结构体、联合体
4. 以及一些其他的语句

预处理器将在第七篇中讲到。编译阶段将不会有预处理指令（#include等）。

我们要处理的语法将在下面列出。

#文法
##定义文法
首先我们定义一条文法是这样的：

NAME ::= SOME_THING

这表示我们定义了一条文法，代号是NAME，可以匹配SOME_THING，比如我们定义

D ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7

表示我们定义八进制数位，可匹配0~7所有的数字，其中竖线|表示或的意思，就是可接受0或1或2或3或…或7。
##文法提取
定义文法可能有很多重复的地方，我们可以提取。

R ::= Ua | Ub | Uc | Ud | ... | Uz

提取成

R ::= U(a | b | c | ... | z)

下面的sizeof的定义将采取这种方式：sizeof((TYPE | ID))表示sizeof(TYPE) | sizeof(ID)
##递归文法
我们要定义一种文法，可以匹配多次的，比如我们要匹配一个八进制整数，显然位数在理想情况下是可以无限长的，为了匹配这种文法，我们引入递归文法，比如定义八进制整数：

N ::= D | ND

表示接受一位8进制数，或者一位8进制数后面继续接8进制整数。那么匹配123的时候就是：

N -> ND -> NDD -> DDD

首先N展开成ND，ND中的N再次展开成ND，最后N展开成D完成匹配。
必须要注意的是我们不能这样定义：N ::= ND，这样就是死递归，停不下来了。

当然我们也可以定义$N ::= D^+$，其中加号顶标表示重复至少一次。

##避免二义性
如果我们这么定义一条文法：

E ::= (E) | E + E | E * E | i

那么匹配i+i*i时就会有两种匹配方式，一种是先匹配+号，另一种是先匹配*号。这条文法没有考虑优先级的问题，就会产生二义性。为了避免二义性，我们修改文法的定义：

E ::= T | E + T | E - T
T ::= F | T * F | T / F
F ::= (E) | i

可以看到我们递归定义时，递归总在运算符的左侧，比如E ::= E + T和T ::= T * F，这样我们展开时就优先左侧展开，就会匹配到(((i + i) + i) + i) + i（括号表示匹配的过程，一个括号是一个E），这表示我们使加号运算符是左结合的，表示运算顺序是从左到右的。如果我们这么定义：S ::= F = S，展开就会是这样：i = (i = (i = (i = i)))，是右结合的，运算顺序是从右到左。定义运算符的左右结合会影响运算的顺序，因此我们要特别注意。

此外上面介绍的这个文法是无歧义的，因为匹配的时候E将只能选择第二种匹配，因为如果选择第一种匹配将不会匹配到加号，为了匹配加号必须选择第二种匹配。因此我们设计文法时要注意使匹配过程只有一种选择。

对于下列文法：

X ::= if (EXPRESSION) STATEMENT
    | if (EXPRESSION) STATEMENT else STATEMENT

如果匹配：

if (...) if (...) ... else ...

将会这么匹配：

if (...) (if (...) ... else ...)
if (...) (if (...) ...) else ...

造成else语句归属不定，这里我们还可以采取匹配的优先级的方式，规定带else第二条匹配方案的优先级更高，消除二义性。

#文法样例

下面将给出一个简化C语言的简单文法（如有纰漏恳求提出）。
注意文法中不应包含预处理器相关的内容。

运算符优先级可参考
http://en.cppreference.com/w/cpp/language/operator_precedence
UNIT_X系列表示运算符相关，依据C++标准，但部分地方进行了微调。

下面的e表示$\epsilon$，即匹配空。

// 常量定义（但不定义负数）
CONSTANT ::= INT_CONSTANT | DOUBLE_CONSTANT
    | STRING | CHARACTER | true | false
// 调用函数时的参数
ARGS_0 ::= e | , UNIT_16 ARGS_0 // EXPRESSION except comma
ARGS ::= e | UNIT_16 ARGS_0 // EXPRESSION except comma
// 定义函数时的参数
PARAM_0 ::= e | , ... // 表示可变参数
    | , TYPE DEF_VAR PARAM_0
PARAM ::= e | TYPE DEF_VAR PARAM_0
// 变量定义
CONSTANT_EXPRESSION ::= EXPRESSION 但不匹配ID
DEF_VAR ::= NAME | DEF_VAR[CONSTANT_EXPRESSION]
PTR ::= * PTR | * const PTR // 指针部分定义如*, *const, **等
DEF_VARS ::= e | , PTR DEF_VAR DEF_VARS
DEF_VARIABLE ::= TYPE PTR DEF_VAR DEF_VARS;
// 表达式，UNIT_X中的X越小优先级越高，ID表示一个标识符
// 我们可能有这种写法：foos[0](some_args)[12]
UNIT_0 ::= CONSTANT | UNIT_0[EXPRESSION] | ID | (EXPRESSION) | UNIT_0(ARGS)
UNIT_1 ::= UNIT_0 // C++ ::
UNIT_2 ::= UNIT_1 | TYPE(EXPRESSION) | sizeof((TYPE | EXPRESSION))
UNIT_3 ::= UNIT_2 | UNIT_2-- ++ // x----是错的，因为x--不是左值，但--操作数必须是左值（即可修改的），但----x是可以的因为--x是左值。所以我们在文法这里就可以限制，写成UNIT_3-- ++也可以，在语义分析阶段报错错误信息会更准确一些。
UNIT_4 ::= UNIT_3 | ++ -- + - ! ~ * & UNIT_4 | (TYPE) UNIT_4 // (TYPE)表示C风格的强制类型转换
UNIT_5 ::= UNIT_4 | UNIT_5 * / % UNIT_4
UNIT_6 ::= UNIT_5 | UNIT_6 + - UNIT_5
UNIT_7 ::= UNIT_6 | UNIT_7 << >> UNIT_6
UNIT_8 ::= UNIT_7 // 不支持C++20 <=>
UNIT_9 ::= UNIT_8 | UNIT_9 < <= > >= UNIT_8
UNIT_10 ::= UNIT_9 | UNIT_10 == != UNIT_9
UNIT_11 ::= UNIT_10 | UNIT_11 & UNIT_10
UNIT_12 ::= UNIT_11 | UNIT_12 ^ UNIT_11
UNIT_13 ::= UNIT_12 | UNIT_13 | UNIT_12
UNIT_14 ::= UNIT_13 | UNIT_14 && UNIT_13
UNIT_15 ::= UNIT_14 | UNIT_15 || UNIT_14
// 注意赋值运算符是右结合的，因此UNIT_9在运算符后面。
UNIT_16 ::= UNIT_15 | UNIT_15 = -= /= *= += &= |=
    ^= %= >>= <<= UNIT_16 | UNIT_15 ? UNIT_16 : UNIT_16
// 逗号表达式
UNIT_17 ::= UNIT_16 | UNIT_17, UNIT_16
EXPRESSION ::= UNIT_17
OPT_EXPRESSION ::= e | EXPRESSION
OPT_STATEMENTS ::= ; | { STATEMENTS }
// 函数定义
DEF_FUNC ::= TYPE PTR NAME(PARAM) OPT_STATEMENTS
DEF ::= TYPE PTR DEF_VAR DEF_VARS
    | TYPE NAME(ARGS) OPT_STATEMENTS
IF_ELSE ::= if (EXPRESSION) STATEMENT
    | if (EXPRESSION) STATEMENT else STATEMENT // 规定如果有else优先匹配这条
FOR ::= for (STATEMENT_FOR; OPT_EXPRESSION; EXPRESSION) STATEMENT
WHILE ::= while (EXPRESSION) STATEMENT
DO_WHILE ::= do STATEMENT while (EXPRESSION);
STATEMENT ::= OPT_EXPRESSION; | { STATEMENTS }
    | DEF_VAR | IF_ELSE | FOR | WHILE | DO_WHILE
    | RETURN | continue; | break;
STATEMENT_FOR ::= EXPRESSION | DEF_VAR
TYPEDEF ::= typedef TYPE PTR ID;
PROGRAM ::= DEF_VARIABLE | DEF_FUNC | TYPEDEF | ;