README.md · mmonsterr/Compilation-principle

# 词法分析部分

返回名称 
读到空格，做一个自循环，不输出二元式 
关键词 
string 
if 
else 
do 
while 
start 
end 
标识符 字母开头 
字符串 “字母序列” 没有数字 注意分号的成对出现 可以为空 
左括号 ( 
右括号 ） 
分隔符逗号 ， 
分隔符分号 ; 
关系运算符 <|>|<>| <=|>=|== 
\= 
连接运算符 + 
重复运算符 * 
[ 
]

# 原产生式

<程序> →<变量说明部分>;<语句部分> 
<变量说明部分> → <变量说明>string<标识符列表> 
<变量说明> → string 
<标识符列表> → <标识符列表>,<标识符>|<标识符> //左 
<标识符> → <字母>|<标识符><字母>|<标识符><数字> 
<语句部分> → <语句部分><语句>;|<语句>; //左 
<语句> → <赋值语句>|<条件语句>|<循环语句> 
<赋值语句> → <标识符>=<表达式> 
<条件语句> → if （ <条件>）<嵌套语句> else <嵌套语句> 
 <循环语句> → do <嵌套语句> 循环语句（ 条件） 
<表达式> → <项>|<表达式><连接运算符><项> //左 
<项>→ <因子>| <项><重复运算符><数字> //左 
<因子> → <标识符>|<字符串>|(<表达式>) 
<字符串> → “<字母序列>” 
<字母序列> → <字母序列><字母>|ε 
<连接运算符> → + 
<重复运算符> → * 
<关系运算符> → <|>|<> |>=|<= |== 
 <条件> → <表达式><关系运算符><表达式> 
 B → start <语句部分> end 
<嵌套语句> → <语句>| B 
<数组>→<标识符> [<数字>] 
~~<字母> → a|b|c|d|e|f|g|h| i |j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z~~ 
<数字> → 0|1|2|3|4|5|6|7|8|9

![image-20221025170402581](C:\Users\mmonsterr\AppData\Roaming\Typora\typora-user-images\image-20221025170402581.png)

# 化简后的产生式

<程序> →string<标识符列表>;<语句部分> 
<标识符列表> → <标识符列表>,<标识符>|<标识符> 
<语句部分> → <语句部分><语句>;|<语句>; 
<语句> → <赋值语句>|<条件语句>|<循环语句> 
<赋值语句> → <标识符>=<表达式> 
<条件语句> → if （ <条件> ）<嵌套语句> else <嵌套语句> 
<循环语句> → do <嵌套语句> while （ <条件> ） 
<表达式> → <项>|<表达式><连接运算符> <项> 
 <项>→ <因子>| <项>重复运算符><数字> 
<因子> → **<**标识符**>**|<字符串>|(<表达式>) 
 <条件>→ <表达式><关系运算符><表达式> 
 <复合语句>→ start <语句部分> end 
<嵌套语句> → <语句>| <复合语句> 
<数字> → 0|1|2|3|4|5|6|7|8|9 //识别出来之后就不需要

# 替换字符表

程序P 
标识符列表I 
标识符i 
语句部分D 
语句S 
赋值语句A 
条件语句C 
表达式E 
<项> F 
复合语句B 
条件L 
循环语句W 
关系运算符r 
数字n 
嵌套语句M 
字符串s 
因子G

# 最终产生式

P →string I; D 
I→iI’ 
I’→,iI’|ε //声明语句done 
D→S;D’ 
D’→S;D’|ε 
S → A| C| W 
A → i= E 
C → if （L） M else M //完成中间代码的生成 
W → do M while （ L） 
E→FE’ 
E’→+FE’|ε 
F→GF’ 
F’→*nF’|ε 
G → i|s|( E) 
L → E r E 
B → start D end 
M → S| B

| A→α | First(A→α） | 更新 |        |
| :-------------------- | :----------------------- | :----------------- | :----: |
| P  →string I; D       | string,#                 |                    |        |
| I→iI’                 | i                        |                    |        |
| I’→,iI’               | ,                        |                    |        |
| I’→ε                  | ;                        |                    |        |
| D→S;D’                | i,if,do                  |                    | 已修改 |
| D’→S;D’               | i,if,do                  |                    | 已修改 |
| D’→ε                  | {end,#}                  | 去掉#              | 已修改 |
| S → A                 | i                        |                    |        |
| S → C                 | if                       |                    |        |
| S → W                 | do                       |                    |        |
| A → i= E              | i                        |                    |        |
| C → if （L） M else M | if                       |                    |        |
| W → do M while （ L） | do                       |                    |        |
| E→FE’                 | i,s,(                    |                    |        |
| E' → +FE'             | +                        |                    |        |
| E’→ε                  | ~~{;,else;while,+,),r}~~ | {;,else,while,),r} |        |
| F→GF’                 | i,s,(                    |                    |        |
| F’→*nF’               | *                        |                    |        |
| F’→ε                  | {;,else;while,+,),r}     |                    |        |
| G → i                 | i                        |                    |        |
| G → s                 | s                        |                    |        |
| G → (E)               | (                        |                    |        |
| L → E r E             | ~~{;,else;while,+,),r}~~ | i,s,(              | 已修改 |
| B → start D end       | start                    |                    |        |
| M → S                 | ~~{;,else;while}~~       | i,if,do            | 已修改 |
| M → B                 | ~~{;,else;while}~~       | start              |        |

# Check Table

| 模块 | 内容 | 实现部分 | 备注 |
| ---------------------- | ------------------------------------------------------------ | -------- | ---------------------- |
| | | **词法分析** | |
| 基本 | 从同目录下的名为in.txt的文件读入源程序 | `void readTxt()` | |
| | 根据词法规则识别单词 | `twoTuple nextInput()` | |
| | 程序内创建并填写相应的表（不要求输出） | `vector<TwoTuple>inputTable` | 在`match()`中获取`presentInput`时产生后`pushback` |
| | 往同目录下名为debug.txt的文件中写入每次识别出的二元式 | `void write2txt(std::string fileName,string content)` | 1.开销比较大（待优化） |
| 拓广 | 如果存在词法错误，则显示词法错误信息、出错位置 | 1.数组的不正确结束，如：a[2 2.字符串的错误结束，如："aaaa | 在进入到字符串的识别的过程中，对代码中 " 的数量进行扫描，若是奇数个，则说明有字符串没有匹配上，调用错误输出程序 1.字符串识别过程中“的失配问题（`netxInput`中）done |
| | | **语法分析** | |
| 基本 | 对源程序作语法分析，确定是否符合该文法 | | done |
| | 往同目录下名为debug.txt的文件中写入每次推导使用的一条产生式 | 使用带参数的宏定义`GEN_STRING();`完成对每条产生式的压入`genString`方便最后输出到`debug.txt` | done |
| 拓广 | 若存在语法错误，显示语法错误信息和位置 | 不符合文法时报错并结束程序 | done |
| | | **语义分析与中间代码生成** | |
| 基本 | 在语法分析的基础上进行语义分析 | | done |
| | 往同目录下名为debug.txt的文件中写入每次产生的四元式， | | done |
| | 分析结束后往同目录下名为debug.txt的文件中写入标识符表、临时变量表和四元式表 | | done |
| | 往同目录下名为out.txt的文件输出源程序的四元式表 | | done |
| 拓广 | 若存在语义错误，显示语义错误信息和位置 |1.赋值给不存在的标识符 2.赋值给越界的数组 3.从数组越界的地方取值，如定义a[2],调用a\[n](n>=2)|done|
| 其他 | 数组功能 |||

| 数组功能 | Description |
| ------------ | ------------------------------------------------------------ |
| 预先修改 | 1.`TwoTuple`和`Identifier`类中均添加成员变量`isArr`和`arrayIndex`，默认为`false`和`0`以及对应的`get set`方法 2.添加获取数组值的函数，参数为`(string name, bool isArr = false, int arrIndex = 0)`,来在标识符列表中寻找以及获取值和越界判断 |
| 词法分析部分 | 在标识符的”流程线“后加入===[===>③0①===数字===>③0②===]===>③0③来进行识别 |
| 语法分析 | 1.声明部分,将数组名称加入标识符列表中,通过成员变量`isArr`和`arrayIndex`来和标识符进行区别 2.通过修改标识符类来进行存储 |
| 语义分析 | 1.声明的时候不允许长度为0的数组 2.取值或者赋值的时候都会进行越界的检测 |

| 报错测试 | 代码 |
| -------------------- | ------------------------------------------------------------ |
| 没有正常结束的字符串 | string a;a="aaa; |
| 字符串不为字母序列 | string a;a="a123a"; string a;a="123a"; |
| 数组长度不可为0 | string a[0] |
| 数组越界 | string a[1];a[1]="a"; |
| 未定义的标识符或数组 | string a;b="a"; string a[3];b[2]="a"; |
| 没有正确结束数组 | string a[3];a[1="a"; |
| 数组匹配失败 | string a[3];a[]="a"; |
| **数组测试** | **代码** |
| 声明与赋值 | string a[3],b[4];a[0]="a";a[1]="b";a[2]="c";b[0]="string";b[1]="b";b[2]=“test";b[3]="test"; |
| 作为条件 | string a[3];a[1]="bb";if(a[1]<>"bb")a[0]="a";else a[2]="ddd"; |

# 数组功能添加

### 	流程分析

词法分析程序读取到  标识符之后返回一个`TwoTuple(type,value)` type用于指出这是个标识符，value用于指定改标识符的值。  
如果读取到的是数组，TwoTuple中保存index。返回的index  
`TwoTuple(string t, string v, bool isArr, int arrIndex =0);`

-   在声明阶段，index用于确定数组的长度
-   在赋值使用阶段，index用于确定更改的数组的位置

语法分析中，通过match("标识符")来确定presentInput是否是标识符，并读头后移。因此需要在match之前

1. `if(twotuple.isArr)`判断当前是否是数组，如果是数组就调用`updatetype`，`identifier`多一个构造函数，传入`name，type,int length=0,bool isArr=false`(添加两个新的成员函数，如果是标识符就`false,length=0`)
1. identifier中添加vector

语义分析中，调用的是`getIdentifier`之后进行`updateValue`，改进：遇到是数组的情况传入name index value  在函数内进行越界的判断

| TwoTuple.h | 说明 |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| `string type` | 存储类型(标识符、字符串、左括号等) |
| `string value` | 存值 |
| `bool isArr` | 如果是数组则为true |
| `int arrIndex` | 存储索引 根据上下文的语义来确定是声明的数组长度还是取值复制的索引 |
| `TwoTuple(string t, string v);` | |
| `TwoTuple(string t, int v);` | 使用**数值**初始化时使用 |
| `TwoTuple(string t, string v, bool isArr, int arrIndex =0);` | 待定 |
| `int getIndex();` | |
| `bool isArray();` | |
| `bool isOF(int t_index);` | 判断是否溢出，应该可以去掉，应该在语义分析部分使用identifier来判断 |
| | |

| identifier.h | 说明 |
| ------------------------------------------------------------ | ---- |
| `string name;` | 存储标识符的名字 |
| `string type;` | 标识符存储东西的类型 |
| `string value;` | 标识符所存储东西的值 |
| `static int indexVar;` | |
| `bool isArr;` | 如果这个标识符用来存储数组，那么则为true |
| `int arr_index;` | 默认为1 |
| `identifier() {};` | 默认构造函数 |
| `identifier(TwoTuple tuple);` | |
| `identifier(string name, string type = "", string value = "");` | |

| nextInput.h                                    | 说明                                                         |
| ---------------------------------------------- | ------------------------------------------------------------ |
| `bool updateType(string name, string type);`   | 传入name和type，在标识符列表中查找是否有该名字的标识符，没有就添加 |
| `auto getArrayValue(string name, int index);`  | 待定                                                         |
| `bool updateValue(string name, string value);` | 更新标识符列表中的标识符的值                                 |
| `identifier getIdentifier(string name);`       | 输入标识符名，从标识符列表中返回该标识符，主要用于获取值     |
| `void backPath(string type, string value);`    | 回填出口                                                     |
| `TwoTuple nextInput();`                        | 词法分析                                                     |

mmonsterr/Compilation-principle

简介

发行版

贡献者

近期动态

mmonsterr/Compilation-principle .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

mmonsterr/Compilation-principle