# 易用版编译器前端生成器C++ **Repository Path**: hao-yiping/LexYacc ## Basic Information - **Project Name**: 易用版编译器前端生成器C++ - **Description**: 拥有原生中文文档的C++语言03标准写的编译器前端生成器。1，它极致轻量级，只有一个源文件和一个头文件，拷贝走就可以用，很少依赖系统库与外部库，连字符串和vector模板都是手工实现。随时插入任何C++项目中。；2，输入文件是json风格。所有的输入规则，清晰简洁，边界严格，不需要记住繁杂的语法糖和对着模糊的手册猜测功能。3，内在的编译器前端工具比如字符串池和抽象语法树。 - **Primary Language**: C/C++ - **License**: MIT - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2025-09-07 - **Last Updated**: 2025-10-12 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 易用版编译器前端生成器C++ ## 介绍 拥有原生中文文档的C++语言03标准写的编译器前端生成器。1，它极致轻量级，只有一个源文件automata.cpp和一个头文件automata.h，拷贝走就可以用，很少依赖系统库与外部库，连字符串和vector模板都是手工实现。随时插入任何C++项目中；2，输入文件是json风格。所有的输入规则尤其是正则表达式规则，清晰简洁，边界严格，不需要记住繁杂的语法糖和对着模糊的手册猜测功能；3，它的输出是高度去耦合的，它并不直接输出一个词法分析器或者文法分析器的代码。而是输出词法分析器和文法分析器的“驱动表”，“状态转移表”等表格。项目内部有依赖于这些表格的一套编译器前端工具比如字符串池和抽象语法树的模板。轻度用户可以使用本项目中完整的工具链进行快速开发得到一个完整的编译器前端。热爱自定义的用户，也可以在得到项目输出的各种表格后自定义编译器前端的各种模块。甚至把这些表格使用在非C++的语言构成的项目中。 ## 简易使用说明 这个项目尚未完工，它是一个已经完工的编译器前端生成器项目（https://gitee.com/hao-yiping/lex.git）的第二个版本。 它的项目根目录有主要的代码文件automata.cpp和automata.h。安装run.sh和运行脚本install.sh。test目录中有test.cpp和main.cpp等等涉及到测试与运行的代码文件。使用者因此有两种使用本软件输出词法分析器和文法分析器的“驱动表”，“状态转移表”等表格，第一种直接下载本项目并且在linux系统中编译运行，第二种，将代码文件automata.cpp和automata.h粘贴到自己的项目中，然后在自己的代码中调用API运行本项目。如果是轻度用户想要使用本项目的工具链，那么还是将代码文件automata.cpp和automata.h以及输出的各种表格粘贴粘合到自己的项目中，就可以完成运行啦。 ### 安装教程 在linux系统中，找到一个你想安放本项目的目录。在bash终端中执行`git clone https://gitee.com/hao-yiping/LexYacc.git`，下载本项目到本地。进入项目的目录，输入`bash install.sh`就可以完成编译了。最简单的安装也就完成了。 想要把拉走automata.cpp和automata.h可以直接在开源网站下载，也可以下载项目到本地后直接在项目的根目录中寻找。 ### 项目结构 项目中还有一些目录，分别是 - ## 简易使用说明 1. xxxx 2. xxxx 3. xxxx ## 输入文件格式 我们的输入文件唯一接受的编码格式是UTF-8。正则表达式构成的词法规则本身也支持匹配UTF-8的字符串。 ### 1. 基础信息 #### 1. 完整的输入文件例子 这是一个完整的输入文件的例子，这个文件在Testfile目录中，是sample.txt。这个文件对应的输出在本文件最后部分。 ``` #lexical:{ operator: { op1: { div: '/'; multi: '*'; } op2: { sum: '+'; sub: '-'; } } #void: { num: ['0'-'9']; letter: ['a'-'z', 'A'-'Z']; } id: id(+5): ( | _) ( | _ | )*; number: {integer: ('-'|'+')?+;} value: value: '='; braket: { left:'('; right: ')'; }; }; #grammar: EXP: { LEFT: id; EXP: LEFT value RIGHT; RIGHT:{ multi(#left, 4): RIGHT [op1] RIGHT; single(1): UNIT; add(#left, 2): RIGHT [op2] RIGHT; //(MULTI * UNIT) } UNIT: { const: integer; xyz: id; alot: left RIGHT right;//(RIGHT) } } ``` #### 2. 保留字与标识符 本软件承认的标识符格式和C语言类似但是不完全相同。本软件承认的标识符格式没有关键字禁用和长度限制。 本软件标识符的格式（命名规则）是严格规定的，必须遵守以下规则，否则会导致编译错误： 1. **组成字符**：只能由字母（A-Z、a-z）、数字（0-9）、下划线（_）三种字符组成，不能包含其他特殊字符（如空格、@、#、-等）。 示例：`abc`、`num123`、`_value` 是合法的；`a-b`、`123var`、`var$` 是非法的。 2. **首字符限制**：第一个字符必须是 **字母或下划线**，不能以数字开头。 示例：`age`、`_count` 是合法的；`1st`、`2name` 是非法的。 3. **大小写敏感**：C语言区分大小写字母，因此大小写不同的标识符会被视为不同的名称。无名生成器与之相同。 示例：`sum`、`Sum`、`SUM` 是三个不同的标识符。 4. **关键字禁用**：所有的起到关键字作用的东西开头都有特殊符号`#`开头与标识符相区分比如`#void`或者`#include`。所以无名生成器没有关键字禁用规则。无 5. **长度限制**：无名生成器不限制标识符的长度。无名生成器的输入文件处理器在存储器空间允许的情况下区分两个任意长度的标识符。 #### 3. 禁止单独输入文法规则 用户可以选择在文件中，只写词法规则，也可以选择在文件中同时写词法和文法规则，但是不能单独的写文法规则。如果用户需要单独的文法规则，那么可以随便写一个补位性质的词法分析规则。词法规则的定义由关键字`#lexical`加上一个冒号开头，所有的词法规则需要被花括号括起来。文法规则的定义由关键字`#grammar`加上一个冒号开头，所有的文法规则需要被花括号括起来。此外文法规则需要在关键字之后指定一个非终结符号作为接受的符号。比如下述例子中的`TEXT`表明`TEXT`符号是是分析器最终接受的符号。 ``` #lexical:{ #void: { num: [0-9]; letter: [a-z]|[A-Z]; } id: id(+5): ( | _) ( | _ | )+; #void: hexa: [0-9] | [a-f] | [A-F]; } #grammar: TEXT: { TEXT： { rules1: ****; rules2: ****; } } ``` 下面是一个缺失了词法规则的输入文件的例子: ``` #grammar: TEXT: { TEXT： { rules1: ****; rules2: ****; } } ``` #### 4. 输入文件的词法与文法 无名生成器分析用户文件所用的词法分析器和文法分析器也是由无名生成器自动生成的。所以在Testfile目录里面，你可以看到本分析器的词法分析和文法分析规则文件`input.txt`。用户可以从此文件实际上包含了大部分输入文件的格式细节与格式规范。 - 输入文件广泛使用C语言风格的花括号，花括号后跟着一个或者零个分号都是许可的。多个分号不合法。 - 每一个正则表达式和文法产生式都以分号结尾。 - 支持Linux系统默认的 LF（Line Feed，换行）格式, 其中字符编码为 '\n'（ASCII 码 10）。也支持Windows系统默认的换行格式，即 ​CRLF（Carriage Return + Line Feed）​，其字符编码为 ​​"\r\n"（ASCII 码 13 和 10）​。 - 输入文件支持C语言风格的注释，这个注释由词法分析器识别后丢弃，具体注释的词法请参阅input.txt。 - 输入文件的词法分析之后丢弃所有的空格换行和水平制表符号。 #### 5. 使用多个输入文件 ##### 5.1简介 `build_v02(const char*file)`方法接受一个可以读的输入文件的文件名，注意不是完整的文件内容而是文件名作为输入。 `build_v02`的改进之处在于它引入了对头文件的支持。 对于一个词法与文法规模庞大的系统，分成多个文件可以更加便捷。 头文件包含的格式是C语言风格的。只支持字符串格式的文件名，尖括号的不支持。 因为这个小小的分析器没有官方库。 比如`#include "extern.h"`是合法的输入，但是`#include `是非法输入。 `#include`中`#`和`include`之间不能有空格，但是`#include `和`"extern.h"`之间可以有任意空格，但是不能换行。 头文件系统的使用原理和C语言的一样都是单纯的文本替换。我们的生成器也不提供比如`#define`之类的宏定义功能。 ##### 5.2头文件中引用头文件 在头文件中可以引用另一个头文件。形成引用的链条。比如以下例子是合法的， 文件source.txt 中包含了头文件lexical.h，lexical.h中包含了头文件unit。 头文件包含并展开后得到了正常的规则文件。 这种引用的链条中同一个文件不能出现两次，更不能成为环形，否则会报错。 source.txt: ``` lexical:{ #include "../data/lexical.h" }; grammar: EXP: { LEFT: id; EXP: LEFT value RIGHT; RIGHT:{ single: MULTI; multi: RIGHT [operator1] MULTI; //(MULTI * UNIT) } MULTI: { single: UNIT; multi: MULTI [operator2] UNIT; //(MULTI * UNIT) } UNIT: { const: integer; xyz: id; alot: left RIGHT right;//(RIGHT) } } ``` ../data/lexical.h: ``` #include "unit" id: id(+5): ( | _) ( | _ | )+; number: {integer: ('-'|'+')?+;} operator1: { sum: '+'; sub: '-'; } operator2: { multi: '*'; div: '/'; } value: value: '='; braket: { left:'('; right: ')'; }; ``` unit: ``` void: { num: [0-9]; letter: [a-z]|[A-Z]; } ``` ##### 5.3头文件的路径 头文件中的名字前可以包含路径。`build_v02(const char*file)`方法输入的文件名中也可以包含路径。 路径的分隔符应该与用户操作系统默认的格式一致。 这个路径可以是绝对路径也可是相对路径。如果是绝对路径，那么当然是无歧义的。 那么如果是相对路径，相对路径的支持规则大致和C语言相同。`build_v02(const char*file)`中如果是相对路径， 那么相对路径是基于调用本生成器进程的当前路径的。 如果一个文件A中使用相对路径引用了文件B那么此路径的出发点是A的路径。仅仅使用B的文件名也视为相对路径。 比如上述例子中`unit`文件的路径其实是`../data/lexical.h`的路径即`../data/unit`。 本软件包在工作的时候不会显示的调用改变进程当前路径的接口。但是会调用fopen函数。 ### 2. 生成词法分析器与正则表达式 #### 1. 基础匹配单元与字符常量 本软件接受的正则表达式的单字符匹配单元可以是ASCII编码的C99标准的单字节ASCII单字符常量，也可以是UTF-8编码C99标准的字符串风格多字节单字符常量。不支持C风格的宽字节单字符常量。所有按照C99标准规定的ASCII单字符字符常量无名生成器都接受。中间没有任何模糊地带，用户有任何疑问可以查阅汗牛充栋的C标准的资料。 - 换言之所有的匹配单元和字符常量都必须用单引号或者双引号包裹。单引号和双引号内部只能包裹一个字符，不允许包裹多个字符。这是我们正则表达式规则设计最独特激进的地方。我们几乎不需要转义字符的概念，任何没有被单引号或者双引号包裹的符号，都用作传递正则表达式的语法和结构，比如改变优先级的括号或者各个通配符等等。以下是一个例子。 ```C intC: i n t; //非法，字符i,n和t没有用单引号包裹。 intC: int; //非法，字符i,n和t没有用单引号包裹并且连成了一个标识符。 intC: 'i' 'n' 't'; //合法。 int:; //合法，这是为数不多的语法糖。 num:[0-9]; //非法，字符0和9 没有用单引号包裹 num:['0'-'9']; //合法 LineFeed: '\n' | '\r\n'; //非法，单引号内同时包裹了两个字符 \r 和 \n。 LineFeed: '\n' | "\r\n"; //非法，双引号内同时包裹了两个字符也不行。 LineFeed: '\n' | '\r' '\n'; //合法 ``` - 转义字符，当我们需要匹配一个特殊的符号比如单引号本身或者换行符的时候我们需要进行转义。进行转义的规则执行C99标准。我们也接受C标准中的八进制字符和十六进制字符常量。一般用户常见的转义字符如下，其余的字符如果有需要请查阅C标准： | 场景 | 转义符 | 含义 | 常见用途 | |--------------|--------|----------------------|------------------------| | 匹配特殊字符 | `\'` | 单引号（避免与包裹符冲突） | 匹配字符串中的单引号，如`'it\'s'` | | | `\"` | 双引号（若支持双引号包裹） | 匹配字符串中的双引号 | | 控制字符 | `\n` | 换行符 | 匹配文本中的换行 | | | `\t` | 制表符 | 匹配表格、代码中的缩进 | | | `\\` | 反斜杠本身 | 匹配路径（如`C:\\file`） | | 可见控制符 | `\r` | 回车符 | 处理Windows换行（\r\n） | ``` null: ''; //非法第0个字符必须转义。 null: '\0'; //合法 ``` - UTF-8匹配单元:单引号`'`仅支持包裹 ASCII 字符（单字节），不可用于 UTF-8 多字节字符；双引号`"`专门用于包裹 UTF-8 多字节单字符（如中文、日文等），且内部同样只能包含一个多字节字符；ASCII 字符是 UTF-8 的子集，因此 ASCII 字符也可使用双引号包裹（如`"0"`等效于`'0'`）。 ```C hello: '你' '好'; //非法，单引号只能包裹ASCII。 hello: "你好"; //非法，字符串风格的多字节单字符常量不是字符串，不能包裹两个字符 hello: "你" "好"; //合法。 num:["0"-"9"]; //合法ASCII也是UTF-8的一个合法子集 LineFeed: '\n' | "\r" '\n'; //合法ASCII也是UTF-8的一个合法子集 LineFeed: '\n' | "\r\n"; //非法，两个ASCII也不行 ``` #### 2. 字符集匹配单元 ##### 2.1 匹配单元集的定义与核心作用 **匹配单元集**（又称“字符集匹配单元”）是基于基础匹配单元（单字符匹配单元）构建的“字符集合容器”，通过方括号`[]`包裹多个基础匹配单元或字符范围，用于实现“匹配任意一个属于该集合的字符”的逻辑。相较于单个基础匹配单元的“单字符匹配”，匹配单元集可通过简洁语法覆盖多个目标字符，大幅简化正则表达式的编写（例如用`['0'-'9']`替代`'0'|'1'|...|'9'`）。 同时，匹配单元集支持“补集”功能（通过`^`符号），用于匹配“不属于该集合的任意字符”，进一步扩展匹配场景（如非数字、非字母的匹配）。 ##### 2.2 匹配单元集的语法规则 ###### 2.2.1 基础构成规则 1. **包裹符号**：必须用方括号`[]`包裹所有内容，无其他合法包裹形式。 2. **内部元素类型**：仅允许包含两类元素，且元素间需用逗号`，`分隔（不可直接连接）： - 单个基础匹配单元：如`'0'`（ASCII单字符）、`"你"`（UTF-8多字节字符）。 - 字符范围：用`-`连接两个同类型基础匹配单元，表示“从左字符到右字符的连续字符集合”（左字符的编码值必须≤右字符，否则非法），如`'0'-'9'`（所有数字）、`'a'-'z'`（小写字母）。 3. **补集规则**：若需表示“补集”（匹配不属于集合的字符），需在`[`后紧跟`^`符号，且`^`仅能出现1次（不可在集合中间或末尾添加`^`，也不可存在多个`^`）。 ###### 2.2.2 优先级与结合性 - 匹配单元集整体作为一个“单匹配单元”参与正则表达式运算，优先级等同于基础匹配单元，可直接与重复后缀（`*`/`+`/`?`/`^{n,m}`）、拼接逻辑或`()`结合使用。 - 集合内部无优先级差异，元素间均为“逻辑或”关系（即匹配任意一个元素即可），即使元素存在范围重叠（如`['a'-'c','b'-'z']`），仍视为合法（重叠部分不影响匹配结果）。 ##### 2.3 合法与非法案例解析 结合实际代码示例，明确匹配单元集的正确用法与常见错误： ###### 2.3.1 正确示范（符合语法规则） ```C #void: // 正确的匹配单元集定义 { // 1. 单个字符范围（ASCII数字） num: ['0'-'9']; // 2. 多个字符范围（小写字母 + 大写字母，用逗号分隔） letter: ['a'-'z', 'A'-'Z']; // 3. 混合“单个字符”与“范围”（小写字母 + 下划线 + 大写字母） idC: ['a'-'z', '_','A'-'Z']; // 4. 补集（匹配非数字字符，^仅在[后第一个位置） NaN: [^'0'-'9']; // 5. 补集（匹配非字母字符） NaL: [^'a'-'z', 'A'-'Z']; } ``` ###### 2.3.2 错误示范（违反语法规则） ```C #void: // 错误的匹配单元集定义 { // 错误1：字符范围“左字符编码 > 右字符”（'9'编码 > '0'，范围无效） num: ['9'-'0']; // 错误2：多个元素未用逗号分隔（直接连接'a'-'z'和'A'-'Z'，语法错误） letter: ['a'-'z' 'A'-'Z']; // 错误3：集合内不可包含重复元素 letter: ['a'-'c', 'b'-'z', 'A'-'Z']; // 错误4：补集符号位置错误（^在[外，应改为[^'0'-'9']） NaN: ^['0'-'9']; // 错误5：补集符号位置错误（^在集合中间，应在[后） NaN: ['0'-'9'^]; // 错误6：补集符号位置错误（^在]外，无意义） NaN: ['0'-'9']^; // 错误7：多个补集符号（集合内不可存在多个^，逻辑矛盾） NaL: [^'a'-'z', ^'A'-'Z']; } ``` ##### 2.4 与基础匹配单元的关联 匹配单元集是**基础匹配单元的“集合化扩展”**，两者的核心区别与联系如下： | 维度 | 基础匹配单元 | 匹配单元集（字符集匹配单元） | |---------------------|---------------------------------------|---------------------------------------| | 核心功能 | 匹配单个字符（ASCII或UTF-8） | 匹配“任意一个属于集合的字符”或“补集” | | 语法形式 | 单引号`'`（ASCII）或双引号`"`（UTF-8）| 方括号`[]`包裹多个元素（单元/范围） | | 元素构成 | 仅1个字符（含转义字符，如`'\n'`） | 多个元素（单元/范围），用逗号分隔 | | 依赖关系 | 独立使用，或作为匹配单元集的内部元素 | 必须基于基础匹配单元构建，不可脱离 | | 示例 | `'0'`、`"你"`、`'\t'` | `['0'-'9']`、`["你","好"]`、`[^'a'-'z']` | ##### 2.5 注意事项 1. **UTF-8字符支持**：匹配单元集同样支持UTF-8多字节字符，需用双引号包裹单个UTF-8字符（如`["你","我","他"]`），可以在范围内使用UTF-8字符（即使字节字符的编码连续性难以保证，如`["你"-"他"]`为和法）。 2. **重复元素禁止性**：集合内不可包含重复元素（如`['0'-'9','5']`）。 3. **与其他语法的结合**：匹配单元集可直接结合重复后缀（如`['0'-'9']+`表示“1个及以上数字”）、逻辑或（如`['0'-'9'] | ['a'-'z']`表示“数字或小写字母”），或通过``引用（如定义`num: ['0'-'9']`后，用``调用）。 #### 3. 基础语法： - 可以用`*`后缀表示重复0次或者任意多次。 - 用`+`后缀表示重复1次或者任意多次。 - 用`?`后缀表示重复0次或者1次。 - 用`^{n,m}`后缀表示重复`n`次到`m`次之间。注意`n`和`m`必须是正整数，并且`m`不能比`n`小。两个数字均不能被省略。 - 可以用`|`表示逻辑或。 - 可以直接连接两个正则表达式表示正则表达式的拼接。 - 后缀的优先级最高，逻辑或的优先级最低，拼接的优先级居中。可以用圆括号`()`将正则表达式的一部分变成整体。 - 可以用尖括号中加标识符的方式``引用上文中已经定义的正则表达式，其中标识符对应正则表达式名。 ``` #void: { num: ['0'-'9']; letter: ['a'-'z', 'A'-'Z']; } id: id（+5）: ( | _) ( | _ | )*; integer: integer: ('+' | '-') ? +; ``` 这一功能正是`#void`组群存在的意义。`#void`组群仅仅被用作后续定义的砖块，而不是词法分析器中识别的词法单元。 - 如果定义的正则表达式名字正是正则表达式本身，那么可以将正则表达式本身省略，这种情况多见于保留字的定义中。注意冒号不能省略。 ```C C_reserved: { int: 'i' 'n''t'; double: 'd''o''u''b''l''e'; } C_reserved_another_defination: { int:; double:; } C_reserved_wrong_defination: { int; //错误。禁止省略冒号。 double; //错误。禁止省略冒号。 } ``` #### 正则表达式的命名 - 每一个输入的正则表达式都需要被命名，它们的名字必须是标识符。每一个被输入的正则表达式都需要被指定一个类型或者说群组，群组名必须是标识符或者保留字`#void`。`#void`群组的正则表达式不会作为词法分析器的输出，而只成为预制的模块，用于简化后续的正则表达式的输入。除了`#void`组,任何两个群组的名字不能重名，任何两个正则表达式的名字也不能重名。所有`#void`群组内的表达式会被合并。命名后跟随的冒号不可省略不可重复。 ``` #void: { num: ['0'-'9']; letter: ['a'-'z', 'A'-'Z']; } id: id(+5): ( | _) ( | _ | )*; #void: hexa: ['0'-'9', 'a'-'f', 'A'-'F'];//两个void组是合法的 ``` 以下的定义是不合法的，视为两个组的重名: ``` reserved: reserved: int； reserved: { double(+5): double; char: char; } ``` - 如果某个组的正则表达式唯一，则可以省略花括号。但是以下的定义是不合法的，组名不会自动成为唯一的正则表达式的名字: ``` id: ( | _) ( | _ | )+; ``` #### 正则表达式的优先级与最长匹配 可以用名称后跟随括号的方法为任何一个非`#void`群组或者任何一个非`#void`群组内正则表达式指定一个优先级。 - 优先级必须是整数并且在32位二进制有符号整数的表示范围之内。 - 数字越大，优先级越高。 - 为群组指定了优先级后依旧可以额外指定群组内的任意一个正则表达式的优先级，覆盖群组的优先级。 ``` reserved(+6): { int: int;// 最终优先级被识别为6 double(5): double; // 最终优先级被识别为5 char: char; // 最终优先级被识别为6 } ``` - 不显式的指定优先级则默认优先级为0。 ``` reserved: { int: int;// 最终优先级被识别为0 double: double(+5); // 最终优先级被识别为5 char: char; // 最终优先级被识别为0 } operator:plus:'+'; // 最终优先级被识别为0 value(+7):plus(5):'+'; // 最终优先级被识别为5 ``` - 如果两个正则表达式接受相同的的字符串，则最终串会被识别为优先级数值更大的正则表达式。优先级不影响最长可接受原则。 ``` #void: { num: ['0'-'9']; letter: ['a'-'z', 'A'-'Z']; } id: id: ( | _) ( | _ | )*; reserved: { int(+5): `i` `n` `t`; } ``` 以以上文法举例子，正则表达式`int`接受C语言的保留字`int`另一个正则表达式`id`接受C语言风格的标识符。那么遇到`"inta"`的时候，无论两个正则表达式优先级如何，`"inta"`都会被识别为标识符。但是如果遇到了字符串`"int"`的时候，这两个正则表达式都是可以被接受的。此时必须为这两个正则表达式指定不同的优先级，如果没有不同的优先级，那么就会导致接受状态冲突，进而导致词法分析器报错。 - 正则表达式的的优先级设置有可能导致无论如何某一个正则表达式都不会成功匹配字符串，进而导致一个接受状态死掉。依旧以上述`int`和`id`为例子。如果`id`的优先级大于`int`，那么无论如何`int`表达式都不会成功匹配字符串。这种状态是不合法的，软件会自动检测这种情况是否出现，如果出现调用`printL`时返回-2。上述例子中想要正常的工作`id`的优先级（数字）必须小于`int`。 ### 3. 文法规则与文法分析器生成 #### 命名规则 文法分析器生成器接受的词法单元（终结符号）正是词法规则中全体非`#void`群组的正则表达式名。所有文法规则依据规则定义的文法符号(非终结符号)自然分组。每一组内的每一个产生式都必须被命名，与词法规则不同的是，同一组内的两个产生式不能重名，而不同组内的两个产生式可以重名。 当然任意两个组名不能重名。非终结符号名必须是标识符，保留字是不合法的。命名后跟随的冒号不可省略不可重复。非终结符号名也不可和终结符号名重名，产生式名字可以和终结符号名重名。 ``` #grammar: TEXT: { LEXICAL: { single: RegGROUP; multi: LEXICAL RegGROUP;}; TEXT: { OnlyL: lexical BEGIN LEXICAL END; LG: lexical BEGIN LEXICAL END grammar colon identifier BEGIN GRAMMAR END;}; RegGROUP: { single: RegGROUPNAME colon RegDEF; multi: RegGROUPNAME BEGIN REGDEFS END; }; BEGIN: colon braceL; //未完 }; ``` 上述例子中`TEXT`, `LEXICAL`, `RegGROUP`, `BEGIN`是定义的非终结符号。注意到`grammar: `后面跟的 `TEXT:`，它是文法分析器最终接受的文法单元对应的非终结符号，这个终结符号的产生式不必定义在最开头。可以将它看作是对整个文法分析规则系统的命名，这是不可缺少的。 一组内可以只有一个产生式。此时可以将花括号去掉，同时规则名自动是非终结符号名。 ``` #grammar: ****: { WRONG: wrong: colon braceL; //非法 CORRECT: colon braceL; //合法 CORRECT: wrong: {colon braceL;} //合法 } ``` 以下的定义是不合法的，视为两个组(非终结符号)的重名: ``` END:{ full: braceR semicolon; half: braceR; } END:{ extra: braceR semicolon semicolon; } ``` #### 产生式定义 每一个产生式体都是单纯的重复非终结符号和终结符号对应的标识符。当然需要用空格分割它们。定义结束后分号是必要的，不可缺少。产生式体中的标识符如果不是词法单元，那么就会被识别为非终结符号，如果分析结束后没有找到此符号的定义则会报错。如果一条规则体是空的，冒号后直接跟着代表结束的分号，那么它可以表示一个空单元。如下文中`legal:;`所示。 ``` EMPTY:{ void: ; } ``` #### 语法糖1:使用一组词法单元 我们在定义词法规则的正则表达式的时候强行要求用户对正则表达式分组。每一组都有组名。我们可以用正则表达式的组名加上方括号来代替具体的某一个正则表达式。 ``` #lexical:{ #void: { num: [0-9]; letter: [a-z]|[A-Z]; } id: id(+5): ( | _) ( | _ | )+; number: {integer: ('-'|'+')?+;} operator1: { sum: '+'; sub: '-'; } operator2: { multi: '*'; div: '/'; } value: value: '='; braket: { left:'('; right: ')'; }; }; grammar: EXP: { LEFT: id; EXP: LEFT value RIGHT; RIGHT:{ single: MULTI; multi: RIGHT [operator1] MULTI; //(MULTI * UNIT) } MULTI: { single: UNIT; multi: MULTI [operator2] UNIT; //(MULTI * UNIT) } UNIT: { const: integer; xyz: id; alot: left RIGHT right;//(RIGHT) } } ``` 这种功能的事项原理是隐形文法符号。 #### 语法糖2:隐形文法符号（非终结符号） 我们有些文法符号我们并不想让它拥有单独的抽象文法树AST上的节点,那么我们可以将它们的名字用尖括号括起来，同时在别的产生式体内引用的时候也要带上尖括号。 ``` Key_Value: id VALUE semicolon; : { value :colon value ; colon :colon ; }; VALUE:{/* ...... */} ``` 这样的文法符号称之为隐形文法符号。当我们的程序构造抽象文法树AST时遇到隐形文法符号对应的节点`B`，会把`B`的全部子节点依次插入到`B`的父节点`A`的子节点数组，然后删去节点`B`。依次插入`B`的子节点数组的起始位置正是`B`的位置。在`B`之后的子节点则依次顺序后延。本程序的输出是词法分析器和文法分析器的驱动表，如果用户可以进一步的调用本程序的语法树构造和词法单元表等功能。对于一个不准备进一步调用本程序的语法树模块的用户，隐形文法符号的用处也许不大。一个符号是否隐形，它在文法分析表中的对应状态无改变。 ``` tree[a]: Key_Value: id VALUE semicolon; child[4]: tree[a + 1] tree[a + 2] tree[a + 3] tree[a + 4]; tree[a + 1]: id; child[0]: tree[a + 2]: : colon value; child[1]: tree[a + 5] tree[a + 6] tree[a + 3]: VALUE: /* ...... */; child[?]: /* ...... */ tree[a + 4]: semicolon; child[0]: tree[a + 5]: colon; child[0]: tree[a + 6]: value; child[0]: ``` 比如上述AST会变成如下的样子 ``` tree[a]: Key_Value: id VALUE semicolon; child[5]: tree[a + 1] tree[a + 5] tree[a + 6] tree[a + 3] tree[a + 4]; tree[a + 1]: id; child[0]: tree[a + 3]: VALUE: /* ...... */; child[?]: /* ...... */ tree[a + 4]: semicolon; child[0]: tree[a + 5]: colon; child[0]: tree[a + 6]: value; child[0]: ``` 使用一组词法单元的实现方式就是自动生成了一个隐形文法符号和它的产生式。这种自动插入会在驱动表的输出中暴露给用户的。对于 ``` RIGHT:{ single: MULTI; multi: RIGHT [operator1] MULTI; //(MULTI * UNIT) } MULTI: { single: UNIT; multi: MULTI [operator2] UNIT; //(MULTI * UNIT) } ``` 我们自动插入: ``` [operator1]: { sum: sum; sub: sub; } [operator2]: { multi: multi; div: div; } ``` 后文通配符产生式的实现原理也是隐形文法符号。也可以将某些文法符号对应的一组产生式的某一个的名字用尖括号括起来，变成隐形产生式。 ``` RIGHT:{ : MULTI; multi: RIGHT [operator1] MULTI; //(MULTI * UNIT) } MULTI: { : UNIT; multi: MULTI [operator2] UNIT; //(MULTI * UNIT) } ``` 对文法符号用尖括号括起来后，再把它的对应的一组产生式的某几个的名字用尖括号括起来，无意义但是也无冲突。程序都把它们全体视作隐形。 #### 语法糖3:通配符产生式 定义正则表达式里面我们常常用的星号和加号来表示一个单元重复任意正数次或任意多次。很多时候一个文法符号的文法规则是另一个文法单元的大量重复，这是我们就可以定义通配符产生式来描述这种情况，就像正则表达式里面那样。 ``` ANY_AA: AA*; Key_ValueS: Key_Value+; ABCD: { manyC: [CC]+; manyC: DD+; AA:AA; } illegal: { illegal: [CC]+ [CC]; illegal: AA DD+; } ``` 但是请注意使用通配符产生式的产生式体只能是一个文法符号(终结符或者非终结符)加上一个通配符，不能出现第三个其余符号。 ``` ANY_AA: [AA]+; ANY_BB: BB*; ``` 会在程序内部转化成； ``` ANY_AA: <[AA]+>; <[AA]+>:{ single:[AA]; multi: <[AA]+> [AA]; } ANY_BB: ; :{ single:void; multi: BB; } ``` ## 输出文件格式 相较于输出一个词法分析器加上文法分析器的完整代码，我们更倾向于输出词法分析器和文法分析器的”驱动表“。这种做法有更高的灵活度。如果用户不像动手写分析器，我们提供两个类将输出的”驱动表“转化为完整代码。 输出的驱动表功能不如输出一个完整分析器功能完全，但是胜在灵活。 如果用户想要进一步的调用驱动表，代码中也提供了支持此驱动表的分析器。 ### 1. 词法分析器输出格式 InputPanel的成员函数`int printL(FILE* fp, const char* nameL)const`输出的词法分析器的驱动表是一个结构体`struct nameL`，的声明和定义，声明格式如下: ``` struct { enum regular { _reg_name_01_ = 1, _reg_name_02_ = 2, // more and more }; enum group { _reg_group_01___ = 1, _reg_group_02___ = 2, // more and more }; static int next(int state, const char c); static int action(int state); static int GroupGet(int state); }; ``` 其中枚举类型`regular`可以帮助将定义的正则表达式名字和它们的编号对应起来，枚举类型`group`可以帮助将定义的正则表达式种类和它们的编号对应起来。两个编号都从1开始。在代码中使用枚举类型代替具体的编号有更好的可读性和可维护性。`static int next(int state, const char c)`则是正则表达式对应的DFA的状态转移函数。它接受当前状态和一个字符，返回DFA的下一个状态。`static int action(int state);`的输入是DFA的状态，返回值是当前DFA的接受状态，如果当前状态没有识别出任何东西则返回0。除了0其余返回值和`enum regular`相对应。`static int GroupGet(int state);`输入一个接受状态，换言之一个`enum regular`，返回当前此法单元对应的群组。三个成员函数内部都无`static`类型变量不申请堆内存，是”纯函数“。 如果`InputPanel`没有正确的完成对输入文件的解析，调用`int printL`返回-1，如果优先级设置问题则返回-2其余返回0。样例输入文件输出的结构体作为一个例子出现在说明的最后部分的附录中。 ### 2. 文法分析表输出格式 InputPanel的成员函数`int printG(FILE* output, FILE* infor, const char* nameG)const;`输出的文法分析器驱动表是一个结构体`struct nameG`，的声明和定义，声明格式如下: ``` struct { enum type { accept = 0, error = 1, push = 2, reduce = 3 }; enum nonterminal { nonterminal_name00 = 0, nonterminal_name01 = 1, //大量重复 nonterminal_namelast = NonTerminalCount - 1 }; enum rules { rules_name00 = 0, rules_name01 = 1, //大量重复 rules_namelast = RulesCount - 1 }; static const size_t StateCount; static const size_t NonTerminalCount; static const size_t TerminalCount; static const size_t RulesCount; static const int GOTO[StateCount][NonTerminalCount]; static const int ACTION[StateCount][TerminalCount]; static const int RulesToSymbol[RulesCount]; static const int RulesLength[RulesCount]; static const char* const RulesName[RulesCount]; static const int Implicit[RulesCount]; }; ``` 其中枚举类型`type`是文法分析动作种类与整数的关系。成员数组`ACTION[StateCount][TerminalCount]`存储当前状态下，当前终结符号下该有的动作。成员数组`GOTO[StateCount][NonTerminalCount]`存储当前状态下，当前非终结符号下该有的动作。存储的`int`值是对4取模得到动作种类，除以整数4才得到具体的动作。对于`GOTO`而言有意义的动作种类只有两个`push`和`error`，然而存储是还是用了四个状态。`RulesToSymbol`存储当前产生式对应的非终结符号，`RulesToSymbol`存储当前产生式的长度，注意如果`void`代表空符号，那么`void`的数目不会计入产生式的长度。`RulesName` 存储当前产生式对应的字符串，这个字符串可以在打印抽象语法树的时候有所帮助。`Implicit`存储对应产生式的是否是隐式的，如果是则为`1`反之为`0`。这个是无名生成器自带的抽象语法树构造器必须的信息。如果用户放弃无名生成器自带的抽象语法树构造器，转而自己构造抽象语法树构造器，这个信息也是有帮助的。 其中枚举类型`nonterminal`可以帮助将定义的非终结符号和程序产生的编号对应起来。其中枚举类型`rules`可以帮助将定义的文法产生式和它们的编号对应起来。可以用枚举类型`rules`寻址`RulesToSymbol`，`RulesToSymbol`，`RulesName`和`Implicit`。可以用枚举类型`nonterminal`寻址`GOTO[StateCount][NonTerminalCount]`第二个维度。样例输入文件输出的结构体作为一个例子出现在说明的最后部分的附录中。隐式的非终结符号和产生式在这两个枚举类型中是被注释的状态，当然用户也可以在看到它们后手动解除注释并且另命它名。 ``` int temp = ::ACTION[top][input[head].accept]; int information = temp / 4; ::type type = (typename ::type)(temp % 4); switch (type) { case ::accept: //分析完成 break; case ::error: //报错 break; case ::push: //移入状态information break; case ::reduce: //规约状态到information int symbol = ::RulesToSymbol[information]; int length = ::RulesLength[information]; //弹出栈顶length个元素，我们规约得到的符号是symbol temp = ::GOTO[stack.top()][symbol]; nextState = temp / 4; nextAction = temp % 4; if(nextAction == ::push) //将nextState压入栈 else //报错 break; } ``` ### 3. `class Morpheme` 使用简介 在得到程序输出的DFA之后可以使用`class Morpheme`对输入的文件或者字符串进行简单的词法分析。 #### 1. 定义概览 在automata.h定义如下: ``` class Morpheme { public: struct result { int accept; int category; size_t length; size_t begin; bool valid; size_t line; }; Morpheme(); ~Morpheme(); char* Copy(size_t site) const; void append(const BufferChar& input, int accept, int category); void AppendEnd(int TerminalCount); void UnitMove(size_t from, size_t to); void CountReset(size_t count); void Demo(FILE* fp) const; size_t GetCount(void) const; const char* GetWord(size_t site) const; const result& operator[](const size_t target) const; char GetChar(size_t site) const; double GetReal(size_t site) const; long int GetInt(size_t site) const; bool& valid(size_t site); template int Build(const char* reg); template int Build(FILE* fp); void clear(void); void copy(const Morpheme& source); size_t initial(void) const; size_t next(size_t index) const; bool still(size_t index) const; int accept(size_t index) const; protected: size_t count; vector lex; vector storage; void SetLine(void); size_t CountEnter(const char* unit); template bool RunBuild(int& accept, BufferChar& result, BufferChar& input, BufferChar& intermediate); }; ``` 其中 `struct result` 是每一个词法单元的信息， `int accept`是词法单元的编号，对应`struct `中的`enum regular`， `category`是词法单元的种类，对应`struct `中的`enum group`。 `size_t length`是词法单元的字符串长度， `size_t begin`是它在存储中首地址的偏移。`valid`记录一个词法单元是否会出现在文法分析中。`valid`默认是`true`，它可以使用`bool& valid(size_t site);`方法进行访问或者手动修改。 `line`是词法单元在代码文本中的行号，行号从`0`开始，如果一个词法单元占据了多个行，那么`line`存储它第一行的行号。行号是词法分析结束后自动进行的。所有的词法单元对应的字符串按输入文件的顺序存储在`protected:vector storage`中。其中每一个词法单元对应的字符串末尾都添加了`'\0'`。`size_t count;`是识别到的词法单元数目，等于`lex.count()`。`lex`存储全体词法单元信息。 #### 2. 对输入进行词法分析 ``` template int Build(const char* reg); template int Build(FILE* fp); ``` 它拥有两个成员函数，分别接受待词法分析输入文件的文件指针或者直接输入一个待词法分析的串。`typename T`即是`printL`打印的类`struct `。 调用例子如下: ``` struct Reg { enum regular{/*definations*/}; enum group{/*definations*/}; static int next(int state, const char c); static int action(int state); static int GroupGet(int state); }; int sample(input) { Morpheme eme; int error; error = eme.Build(input); eme.Demo(stdout); return error; } ``` 运行成功返回值是`0`。然而这个过程几乎不会返回其他值，遇到未见的词法单元会将它们识别为未见单元，未见单元的`accept`值是0。 #### 3. 常用成员函数 `void Demo(FILE* fp) const;`展示词法分析的结果。 `const result& operator[](const size_t target) const;`返回第`target`个词法单元信息，合法范围是从`0`到`count-1`。不做范围检测。 `const char* GetWord(size_t site) const;`返回第`target`个词法单元对应的字符串在`all`中的首地址。`target`合法范围是从`0`到`count-1`。不做范围检测。不可以对返回的指针释放内存。 `char* Copy(size_t site) const;`返回第`target`个词法单元对应的字符串。`target`合法范围是从`0`到`count-1`。不做范围检测。使用结束后应该对返回的指针释放内存。此成员函数返回的字符串指针的内存由`malloc`分配。 `size_t GetCount(void) const;` 返回成员变量`size_t count;`的值。 `void clear(void);` 清空当前类中内容，但是不释放占据存储。 `void copy(const Morpheme& source);`拷贝一个词法分析结果。 #### 4. 返回下一个词法单元 有时候丢弃一些词法单元可以方便文法分析，这些词法单元包括空格换行注释TAB等等。`result.valid`记录一个词法单元是否会出现在文法分析中。它可以使用`bool& valid(size_t site);`方法进行访问或者手动修改。没有用户修改时`result.valid`默认是`true`。使用`size_t initial(void) const;`方法返回第一个`valid`设置为`true`的词法单元的地址偏移。 使用`size_t next(size_t index) const;`方法返回地址偏移为`index`的下一个`valid`设置为`true`的词法单元的地址偏移 。 使用`bool still(size_t index) const;`方法返回地址偏移`index`是否还在合法范围(`0`到`count-1`)之内。 使用`int accept(size_t index) const;`方法返回地址偏移为`index`的词法单元的编号。(对应`struct `中的`enum regular`)。 ### 4. `class GrammarTree` 使用简介 这个类对应一个抽象语法树。 #### 1. 定义概览 在automata.h定义如下: ``` class GrammarTree { public: GrammarTree(); ~GrammarTree(); struct TreeInfor { bool rules;// rules: false —— 此为叶子节点，对应词法终结符（lexical terminal symbol）， size_t site;// site 表示该词法单元在词法表中的位置（即 Morpheme::storage 中的索引） size_t label;// rules: true —— 此节点可能为非叶子节点（对应产生式规则）， void* infor; // site 表示对应的产生式规则编号（即 T::RulesToSymbol 中的索引） }; void Demo(FILE* fp, const Morpheme& input, const char* const* RulesName) const; void clear(void); template int build(const Morpheme& input); tree* GT; bool error_record00; size_t error_record01; size_t error_record02; protected: }; template class tree { public: tree(); ~tree(); void clear(void); void build(vector*>& input); void build(vector*>& input, size_t offset); void PostOrderTraversal(vector*>& output); T& root(void); const T& root(void) const; size_t ChildCount(void) const; tree* child(size_t No) const; struct Iterator { tree* target; int state; }; class PostIterator { public: PostIterator() {} ~PostIterator() {} void initial(tree* root); int& state(void); tree*& target(void); void next(void); bool still(void); protected: vector stack; }; private: array*> childs; T content; tree* parent; size_t No; }; ``` #### 2. 对输入进行文法分析 ``` template int build(const Morpheme& input); ``` 它拥有一个成员函数别接受待词法分析结果`const Morpheme& input`作为输入的串。`typename T`即是`printG`打印的类`struct `。它通过`void Demo(FILE* fp, const Morpheme& input, const char* const* RulesName) const;` 可以在屏幕打印输出，输出需要一个字符串数组`const char* const* RulesName`作为参数。 调用例子如下: ``` struct Reg { enum regular{/*definations*/}; enum group{/*definations*/}; static int next(int state, const char c); static int action(int state); static int GroupGet(int state); }; struct Panel { enum type{/*definations*/}; enum nonterminal{/*definations*/}; enum rules{/*definations*/}; static const size_t StateCount; static const size_t NonTerminalCount; static const size_t TerminalCount; static const size_t RulesCount; static const int GOTO[StateCount][NonTerminalCount]; static const int ACTION[StateCount][TerminalCount]; static const int RulesToSymbol[RulesCount]; static const int RulesLength[RulesCount]; static const char* const RulesName[RulesCount]; static const int Implicit[RulesCount]; }; int sample(input) { Morpheme eme; GrammarTree Tree; int error; error = eme.Build(input); if (error != 0) return error; eme.Demo(stdout); error = Tree.build(eme); if (error != 0) return error; Tree.Demo(stdout, eme, Panel::RulesName); return error; } ``` #### 3. 遍历语法树做您想做的 可以使用类型`iterator`帮助遍历语法树，示例代码如下。 ``` void sample(GrammarTree & input) { tree* now; hyperlex::tree* Tree; hyperlex::tree::PostIterator iterator; iterator.initial(input.GT); while (iterator.still()) { now = iterator.target(); if (iterator.state() == 0) { // 先序经过now节点 } else { // 后序经过now节点 } iterator.next(); } } ``` #### 4. 文法分析报错 成功的文法分析返回0。否则返回`static const int GOTO[StateCount][NonTerminalCount];`或者`static const int ACTION[StateCount][TerminalCount];`中对应的报错单元。当文法分析报错时`error_record01`记录文法分析中报错时遇到的下一个词法单元的位置，`error_record02`记录文法分析中报错时当前栈顶的状态。`error_record00`如果真，则是`ACTION`报的错，反之是`GOTO`报的错。 将报错信息变的人类可理解是个LR文法分析中的麻烦问题。本软件在这个领域做的很少，功能不强。 ## 软件架构简介与版本 ### 已知问题 - 开发未完成。目前只有旧版程序可用。 - 由于无名生成器分析用户文件所用的词法分析器和文法分析器也是由无名生成器自动生成的。为了完成这一自举，代码中留下了很多无用的脚手架。 ### 代码约定 - 1 C++ 03 标准 - 2 尽可能少的依赖 STL等等C++的标准库 - 3 暴露在外的接口命名均为小写字母开头的驼峰式命名法 - 4 内部实现命名相对自由 - 5 内存分配失败后直接 abort() - 6 所有的类不会抛出异常，仅仅使用C风格的错误码 - 7 所有的非POD的类均支持拷贝构造，拷贝赋值与move的成员函数 - 8 所有的模板与容器均在 hyperlex 命名空间下，它的使用者必须显式使用 hyperlex:: 前缀 不得使用 using namespace hyperlex;因为这些模板与容器一定与 STL 等标准库冲突 这些模板的功能与接口与 STL 常常不同，所以仅仅用于本库内部，用户直接使用于自身代码库风险较高。 - 9 所有的“平凡析构”类型默认不可以被标记为可位搬迁的类型 - 10 项目不使用任何static类型，也没有任何的线程锁。项目内没有任何的全局变量，不显式的创造多线程 - 11 每一个手册上暴露在外的接口合法供用户使用的接口都可以视为某种原语，线程安全。 用户可以在多线程中使用这些原语，但必须保证每一个原语的调用是原子的。 例如：用户可以在多个线程中同时调用 dictionary::search()，但不可以在一个线程中调用 dictionary::search() 的同时 在另一个线程中调用 dictionary::insert()。