# pasex **Repository Path**: icerupt/pasex ## Basic Information - **Project Name**: pasex - **Description**: No description available - **Primary Language**: C++ - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2016-04-25 - **Last Updated**: 2020-12-19 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README = 编译原理课程设计报告 徐旗江 学号 913106840320 班级 9131065502 :toc: <<<< == 使用说明 从文件 `3-grammar` 读入正规文法，从文件 `2-grammar` 读入上下文无关文法， 从 `input-program` 读入程序，这些文件都放在当前目录下，然后运行就可以得到 结果。程序中的一个宏开关 `ALL_TOKEN` 如果设置成1可以输出所有token表即使 程序不能通过编译。可执行程序就是当前目录下的main。 `c++` 的编译指令是: `clang++ -o main -std=gnu++14 -O3 -Wall -Wextra -march=native main.cc src/pasex.cc src/parse.cc` 当然也可以用别的编译器。 == 文法输入规范 项目的测试语言是https://www.cs.helsinki.fi/u/vihavain/k06/okk/items/minipascalsyntax.html[minipas], 虽然使用minipas进行测试，但是项目本身不局限于具体的语言。minipas的递归下降语法以及词法的BNF定义在 上面的链接里。我们将其翻译成了相应的上下文无关文法以及正规文法作为程序(词法析器和语法分析器)的输入。 我们输入的文法的文件，每行是一条对应文法的产生式，可以有空行，每个文法符号 用空格隔开，一段连续的字符串就是一个文法符号。 对于正规文法我们扩充了文法，允许产生式右部第一个文法符号为仅推出终结符的 非终结符以减少文法长度。 === 文法符号定义 |=== |文法符号第一个字符 |含义 |! |文法开始符 |$ |非终结符 |@ |词法分析器识别的非终结符 |其他 |终结符 |=== <<<< == 整体架构 先由二型文法和三型文法初始化好相应的dfa， 整个语法分析过程由语法分析器的 `parse::lr_set_dfa::parse()` 不断调用词法分析器 的 `lex::dfa::lex()` ， `lex()` 每次返回一个token对，作为语法分析器的输入流 不断进行LR(1)分析。 === 项目目录结构 项目主要内容的目录结构如下： .tree ---- . ├── readme.asciidoc ├── input-program ├── 2-grammar ├── 3-grammar ├── doc │   ├── input-syntax │   └── minipas ├── output-graph │   ├── dfa-out.dot │   ├── dfa.png │   ├── nfa-out.dot │   └── nfa.png ├── src │   ├── parse.cc │   ├── parse.hh │   ├── pasex.cc │   └── pasex.hh ├── main ├── main.cc ---- <<<< == 词法分析器 pasex === 词法所需结构体 首先看下词法分析器里定义的所有结构。 |=== |结构名称 |含义 |`lex::symbol` |文法符号 |`lex::regular_rule` |正则产生式 |`lex::regular_grammar` |正则文法 |`lex::nfa::nfa` |不确定有限状态机 |`lex::dfa::dfa` |确定有限状态机 |=== 我们重点介绍下nfa和dfa。 === nfa ==== nfa接口声明 我们来看下nfa里主要的接口。 |=== |函数声明 |含义 |`nfa(regular_grammar const & g);` |nfa构造函数，通过一个正则文法构造nfa |`std::pair closure(state const & s) const;` |返回一个nfa节点的epsilon闭包 |`state trans(state const & s, char ch) const;` |返回一个状态集经过一个字符转移后的状态集合 |`void add_edge(int u, int v, std::string const & s);` |在nfa上增加一条边 |=== nfa的构造过程比较简单，对于形如 `$A->a $B` 只需要从 `$A` 的节点连向 `$B` 节点 一条标为 `a` 的边， 如果是形如 `$A->a` 的需要连一条从 `$A` 节点到终态节点为 `a` 的边， 形如 `$A->epsilon` 的只需要将节点 `$A` 标为终态。 假如说我们要是别的是 `@identifier` 和 `@keyword` 两个状态，那么我们最终的nfa 是类似 (`@identifier` | `@keyword`)* 这么一条正则产生式所对应的nfa，所以我们 用正则产生式产生nfa的方法时给它隐含的加入了一个开始符，通过epsilon边连向这些 要识别的状态。还需要注意的是对于标记为要是别状态的节点，需要在终态节点上维护 相应是别状态的标记(flag)。 ==== nfa状态图 这个是简化数字字母得到的nfa的状态图。 image::nfa.png[caption="Figure 1: ", title="NFA", alt="NFA", width="1000", height="2000"] === dfa ==== dfa接口声明 我们来看下dfa里主要的接口。 |=== |函数声明 |含义 |`dfa(nfa::nfa const & n);` |dfa构造函数，通过一个nfa构造nfa |`token_type lex(std::string const & str, std::string::iterator & it);` |返回从代码当前位置开始lex得到的一个token键值对 |`void add_edge(int u, int v, char ch);` |在dfa上增加一条边 |=== dfa的构造过程是一个bfs的过程，从nfa开始节点的闭包开始，枚举字母表向后转移 一个字符，然后得到一个nfa节点集合，再求这个集合的闭包，那么就可以从当前闭包 对应dfa的节点连一条转移字符的边到求得闭包对应的节点。 lex是词法分析的主要过程，由语法分析器调用，一次调用返回程序当前位置开始得到的 一个token。 ==== dfa状态图 这个是简化数字字母得到的确定化nfa后的dfa的状态图。 image::dfa.png[caption="Figure 2: ", title="DFA", alt="DFA", width="1000", height="2000"] <<<< == 语法分析器 parse === 语法分析所需结构体 首先看下语法分析器里定义的所有结构。 |=== |结构名称 |含义 |`parse::symbol` |文法符号 |`parse::context_free_rule` |上下文无关产生式 |`parse::context_free_grammar` |上下文无关文法 |`parse::ex_context_free_rule` |拓展的上下文无关产生式（增加点的位置） |`lr_set_base` |LR项目集族的核心 |`lr_set` |LR项目集族 |`lr_set_dfa` |LR项目集族dfa |=== === LR项目集族dfa接口声明 我们重点介绍下LR项目集族dfa的接口。 |=== |函数声明 |含义 |`lr_set_dfa(context_free_grammar const & cfg)` |lr_set_dfa构造函数，通过一个上下文无关文法构造dfa |`bool acc(int state);` |判断当前栈顶状态是不是acc状态 |`void add_edge(int u, int v, symbol const& s);` |在dfa上增加一条边 |`int rr_conflict_count() const;` |dfa中有规约规约冲突的项目集族的个数 |`int sr_conflict_count() const;` |dfa中有移进规约冲突的项目集族的个数 |`bool parse(std::string const & s, lex::dfa::dfa & d);` |语法分析的主过程，进行parse |=== LR项目集族dfa的构造函数如下： [[app-listing]] [source, cpp] ---- lr_set_dfa::lr_set_dfa(context_free_grammar const & cfg) { context_free_rule cfr(cfg.start_ex, {cfg.start}); lr_set_base lsb; lsb.add(ex_context_free_rule(cfr, 0), symbol("#")); node_index(lr_set(lsb, cfg)); for (int i = 0; i < (int)all.size(); i++) { int id = node_index(all[i]); std::map tmp; for (auto ls : all[i].lrs) { if (ls.first.point == (int)ls.first.r.rhs.size()) continue; auto tt = ls.first; tt.point++; tmp[ls.first.r.rhs[ls.first.point]].add(tt, ls.second); } for (auto i : tmp) add_edge(id, node_index(lr_set(i.second, cfg)), i.first); } } ---- 首先通过扩充文法，求得该扩充产生式的LR项目集闭包，然后不断枚举当前dfa上节点， 每次枚举项目集族中的产生式，如果是规约式就跳过，然后对于移进相同文法符号的 产生式通过 `std::map` 合并，得到LR项目集的核心，然后求该核心的闭包，就可以得到 两个节点的编号，然后就能通过 `add_edge` 函数给dfa加一条边。 语法分析过程维护两个栈，状态栈和符号栈，在dfa上根据当前调用lex得到的文法符号 来决定是往下移动还是规约。如果有出边就移动到相应状态上，当前状态入栈以及文法符号 入栈，如果当前文法符号在某个可规约式的前向搜索符里，就可以进行规约, 然后状态会退， 再把规约后得到的文法符号入栈，移到相应状态上。最后如果在acc状态就是成功编译。 其他情况就会报错并停止。 <<<< == 使用实例 === 词法分析 我们用词法分析分析下面这段pascal代码： [[app-listing]] [source, pascal] ---- var da:array[0..1000]of longint; d2:array[0..16]of longint; i,j,n,m,k,d,n2,x,s,ans,max,t,kk:longint; begin readln(n,d,k); d2[0]:=1; for i:=1 to d+1 do d2[i]:=d2[i-1]*2; for i:=1 to n do begin read(m); for j:=1 to m do begin read(s); da[i]:=da[i]+d2[s-1]; end; end; n2:=d2[d]; max:=0; t:=0; writeln(max); end. ---- ==== 输出token表 将 `main.cc` 中的 `ALL_TOKEN` 宏开关设置成1我们得到结果运行如下： .... token table: @keyword var @delimiter ^ @identifier da @delimiter : @keyword array @operator [ @integer-literal 0 @delimiter .. @integer-literal 1000 @operator ] @keyword of @delimiter ^ @type-identifier longint @delimiter ; @delimiter ^ @identifier d2 @delimiter : @keyword array @operator [ @integer-literal 0 @delimiter .. @integer-literal 16 @operator ] @keyword of @delimiter ^ @type-identifier longint @delimiter ; @delimiter ^ @identifier i @delimiter , @identifier j @delimiter , @identifier n @delimiter , @identifier m @delimiter , @identifier k @delimiter , @identifier d @delimiter , @identifier n2 @delimiter , @identifier x @delimiter , @identifier s @delimiter , @identifier ans @delimiter , @identifier max @delimiter , @identifier t @delimiter , @identifier kk @delimiter : @type-identifier longint @delimiter ; @delimiter ^ @keyword begin @delimiter ^ @keyword readln @operator ( @identifier n @delimiter , @identifier d @delimiter , @identifier k @operator ) @delimiter ; @delimiter ^ @identifier d2 @operator [ @integer-literal 0 @operator ] @operator := @integer-literal 1 @delimiter ; @delimiter ^ @keyword for @delimiter ^ @identifier i @operator := @integer-literal 1 @delimiter ^ @keyword to @delimiter ^ @identifier d @operator + @integer-literal 1 @delimiter ^ @keyword do @delimiter ^ @identifier d2 @operator [ @identifier i @operator ] @operator := @identifier d2 @operator [ @identifier i @operator - @integer-literal 1 @operator ] @operator * @integer-literal 2 @delimiter ; @delimiter ^ @keyword for @delimiter ^ @identifier i @operator := @integer-literal 1 @delimiter ^ @keyword to @delimiter ^ @identifier n @delimiter ^ @keyword do @delimiter ^ @keyword begin @delimiter ^ @keyword read @operator ( @identifier m @operator ) @delimiter ; @delimiter ^ @keyword for @delimiter ^ @identifier j @operator := @integer-literal 1 @delimiter ^ @keyword to @delimiter ^ @identifier m @delimiter ^ @keyword do @delimiter ^ @keyword begin @delimiter ^ @keyword read @operator ( @identifier s @operator ) @delimiter ; @delimiter ^ @identifier da @operator [ @identifier i @operator ] @operator := @identifier da @operator [ @identifier i @operator ] @operator + @identifier d2 @operator [ @identifier s @operator - @integer-literal 1 @operator ] @delimiter ; @delimiter ^ @keyword end @delimiter ; @delimiter ^ @keyword end @delimiter ; @delimiter ^ @identifier n2 @operator := @identifier d2 @operator [ @identifier d @operator ] @delimiter ; @delimiter ^ @identifier max @operator := @integer-literal 0 @delimiter ; @delimiter ^ @identifier t @operator := @integer-literal 0 @delimiter ; @delimiter ^ @keyword writeln @operator ( @identifier max @operator ) @delimiter ; @delimiter ^ @keyword end @delimiter . .... 其中 `^` 表示的空白符。 === 语法分析器 还是上面的代码, 我们将 `main.cc` 中的 `PARSE` 宏开关设置成1我们得到结果运行如下： .... [ OK ] no error occured. .... 得到了一个通过语法分析的反馈。 如果我们分析下面这段错误的代码： [[app-listing]] [source, pascal] ---- var da:array[0..1000]of longint; begin d1:="123"; d2:="\"\\"; d3:=123.3123e-123; readln(n,d,k); for i:=1 to n do begin read(m); for j:=1 to m do begin read(s); da[i]:=da[i]+d2[s-1]; end; end; writeln(max); wroteln(max); end. ---- 如果打开语法分析中的 `ENABLE_DEBUG` 开关，就可以看到token流停止在 .... @identifier wroteln @operator ( .... 并且输出了 `[FAIL] some errors occured.` 表示语法分析出错。