类C语言词法分析器设计与实现

1. 词法分析概述

词法分析是编译器前端的第一阶段，其任务是将源程序字符流分解成有意义的词素，并生成词法单元序列。

2. 类C语言语法描述

2.1 关键字

类C语言中共有20个关键字，如下表所示：

| 序号 | 关键字 | 序号 | 关键字 | |---|---|---|---| | 1 | begin | 11 | if | | 2 | do | 12 | else | | 3 | while | 13 | select | | 4 | for | 14 | case | | 5 | int | 15 | break | | 6 | string | 16 | return | | 7 | double | 17 | end | | 8 | bool | 18 | write | | 9 | char | 19 | read | | 10 | float | 20 | |

2.2 运算符

类C语言中的运算符如下表所示：

| 序号 | 运算符 | 序号 | 运算符 | |---|---|---|---| | 21 | + | 31 | <> | | 22 | - | 32 | > | | 23 | * | 33 | >= | | 24 | / | 34 | < | | 25 | ** (乘方) | 35 | <= | | 26 | % (求余) | 36 | ! | | 27 | = (赋值) | 37 | && | | 28 | += | 38 | || | | 29 | -= | 39 | ++ | | 30 | == | 40 | -- | | | | 41 | ， | | | | 42 | - (负号) | | | | 43 | & | | | | 44 | % (格式运算符) |

2.3 分界符

类C语言中的分界符如下表所示：

| 序号 | 分界符 | 序号 | 分界符 | |---|---|---|---| | 45 | ( | 48 | ; | | 46 | ) | 49 | ' | | 47 | , | 50 | ' |

2.4 标识符

标识符的构词规则为：以大写字母 (A-Z) 或小写字母 (a-z) 开头，后面可以跟大写字母或小写字母或数字 (0-9) 或下划线。如果有下划线，只能出现一次，长度最多为15个。区分大小写。

2.5 常量

常量分为整型、实型、字符型、字符串型、布尔型。其中整型常量包括十进制、八进制和十六进制，实型包括十进制和科学计数法。

整型常量八进制、十进制和十六进制与C语言要求一致。
实型常量要求与C语言要求一致。注意小数点的个数。
字符类型和字符串类型常量要求与C语言要求一致。
布尔型常量有2个，分别是 TRUE 和 FALSE。

3. 词法分析程序设计

3.1 单词构词规则的正规式或正规文法

关键字：begin|do|while|for|int|string|double|bool|char|float|exit|if|else|select|case|break|return|end|write|read
标识符：(a|b|c|...|z|A|B|C|...|Z)(a|b|c|...|z|A|B|C|...|Z|0|1|2|...|9|_)
常量：
- 整型常量：(0|1|2|...|7)(0|1|2|...|7)*|0(x|X)(0|1|2|...|9|a|A|b|B|c|C|d|D|e|E|f|F)*|0
- 实型常量：(0|1|2|...|9).(0|1|2|...|9)+(e|E)(+|-|ε)(0|1|2|...|9)+
- 字符型常量：'(a|b|c|...|z|A|B|C|...|Z|0|1|2|...|9|_| | |\|'|'|...)'|'\'(a|b|c|...|z|A|B|C|...|Z|0|1|2|...|9|_| | |\|'|'|...)'
- 字符串型常量：'(a|b|c|...|z|A|B|C|...|Z|0|1|2|...|9|_| | |\|'|'|...)*'

3.2 NFA和DFA图

（见附图）

3.3 词法分析程序的整体方案设计

数据结构选择: 使用链表作为符号表的数据结构，每个节点包含单词的类别和值。
符号表的大小设置: 根据实际需要确定符号表的大小，可以根据标识符的数量来设置。
输入源程序和输出结果的存储: 将源程序以字符串形式存储，输出结果以链表形式存储。
标识符和关键字的区分识别: 在词法分析程序中，遇到标识符时先判断是否为关键字，再存入符号表中。
两个字符组成的运算符的识别: 通过判断两个字符是否为运算符来识别，如'+='。
负号和减号的区分: 通过判断负号前面是否为数字或标识符来区分负号和减号。
单词拼写错误的实现: 通过对比识别出的单词和关键字、运算符、分界符、常量等进行匹配，如果不匹配则认为是拼写错误。

3.4 测试用例源程序

int main()
begin
  int a = 10;
  int b = 20;
  int c = a + b;
  if (c > 30)
    write('%d', c);
  else
    write('Error');
  end

3.5 识别关键字和标识符类单词的代码、及识别整型实型常量单词的代码

import re

keywords = ['begin', 'do', 'while', 'for', 'int', 'string', 'double', 'bool', 'char', 'float', 'exit', 'if', 'else', 'select', 'case', 'break', 'return', 'end', 'write', 'read']

def is_keyword(word):
    return word in keywords

def is_identifier(word):
    pattern = re.compile(r'^[a-zA-Z_][a-zA-Z0-9_]{0,14}$')
    return re.match(pattern, word)

def is_integer_constant(word):
    pattern = re.compile(r'^(0|[1-9][0-9]*|0[0-7]+|0[xX][0-9a-fA-F]+)$')
    return re.match(pattern, word)

def is_real_constant(word):
    pattern = re.compile(r'^([0-9]+.[0-9]*|[0-9]*.[0-9]+)([eE][+-]?[0-9]+)?$')
    return re.match(pattern, word)

# Test
print(is_keyword('begin'))  # True
print(is_keyword('while'))  # True
print(is_keyword('main'))   # False

print(is_identifier('a123'))    # True
print(is_identifier('_abc123')) # True
print(is_identifier('123abc'))  # False

print(is_integer_constant('123'))       # True
print(is_integer_constant('0xFF'))      # True
print(is_integer_constant('0123'))      # True
print(is_integer_constant('123456789')) # True
print(is_integer_constant('01a'))       # False

print(is_real_constant('3.14'))           # True
print(is_real_constant('0.123'))          # True
print(is_real_constant('1.23e+10'))       # True
print(is_real_constant('1e-10'))          # True
print(is_real_constant('10.'))            # True
print(is_real_constant('.123'))           # True
print(is_real_constant('3.14.15'))        # False

3.6 词法分析程序的运行结果截图

（见附图）

3.7 输出结果中单词类别的说明

1-20：关键字
21-44：运算符
45-50：分界符
51：标识符
52：整型常量
53：实型常量
54：字符型常量
55：字符串型常量
56：布尔型常量

4. 实验体会

在设计词法分析程序时，需要仔细考虑各种单词的构词规则，尤其是常量的表示方式，需要根据C语言的规范进行处理。
在实现词法分析程序时，需要注意处理单词之间的空格和换行符，以及处理注释等特殊情况。
在设计测试用例时，需要覆盖各种情况，包括各类单词、拼写错误等，以便验证词法分析程序的正确性。