查看原文
其他

一起学编译|LL(1) 语法分析器解析算数表达式生成AST

菜鸟级X 看雪学院 2019-05-25


为什么学习编译原理


因为前一段时间一直在研究VMP,把VMP的大致结构看了一下。个人认为,提取伪代码其实稍微花一些功夫就可以提取出来的,代码混淆也不是什么难题,难的是几行汇编代码变成了成千上万行虚拟代码。现在VMP分析插件基本上可以提取出2.x版本的伪代码,但是真的要使用VMP分析插件去分析一个稍微复杂一点的程序,这个工作量不敢想象,虽然做了模板匹配但是数量级在这里。


所以我一直在想一个解决方案,经过了一段时间的思考我想到了一个解决方案,但是我不知道是否有人尝试过这么干。或者说尝试过,已经放弃(失败了)。


我的想法是:


  • 首先VMP是什么?

  • VMP在加壳虚拟化代码的时候显示的为什么是程序编译中?

  • 仔细想想编译器是什么?


C语言编译器 就是把程序员能看懂的C语言代码翻译成机器能看懂的汇编代码。


而VMP编译器就是把机器能看懂的汇编代码翻译成VMP虚拟机能看懂的代码。

 

试想是否可以写一个反VMP编译器。就是把VMP代码再次编译成机器能看懂的汇编代码? 可行性我现在不能100%的确定,但是理论上是可以实现的。只不过是时间长短的问题。 比如说VMP的虚拟栈分析我的一些看法是:

 

比如一段VMP代码:


vPushImm4 100
vPushReg  r1
vPopReg r2
vPushImm 200
vPopReg r3

 

默认有一个栈偏移


SP = 0


1、当vPushImm 100 执行的时候这个时候提取出 两个词法单元


  • (vPushImm4)


  • (IMM, 100) // IMM 是立即数, 4是词法单元的属性

    当我们看到vPushImm4的时候可以当做生成了一个临时变量。

    首先把 SP + 4。

    SP = SP + 4 

    然后生成一个中间变量

    vLocal4 = 100 // 这个vLocal4 中的4就是SP的偏移


2、执行 vPushReg r1 的时候同样也是生成一个变量

SP = SP + 4

生成中间变量

vLocal8 = r1


3、执行 vPopReg r2 的时候获取到两个词法单元

vPopReg

r2

此时把当前SP的值给r2,然后SP = SP - 4

生成类似的代码

r2 = vLocal8

SP = SP - 4 (此时SP = 4)


4、执行 vPushImm4 200的时候

SP = SP + 4 (此时SP = 8)

生成代码

vLocal8 = 200


上述的VMP语句综合起来就是

vLocal4 = 100

vLocal8 = r1

r2 = vLocal8

vLocal8 = 200


如果在应用 机器无关优化的话:

vLocal4 = 100

r2 = r1

vLocal8 = 200


当然更加具体的,我学习的还没有那么深入。还没学到中间代码生成,我是先有这个想法再去学编译原理的。现在看到语法翻译的部分。我会的东西都会发帖子出来的。有一起学的朋友可以留言一起。



进入主题LL(1)语法分析器


首先给出LL(1)文法的定义



LL(1)文法是一个自顶向下语法分析算法,自顶向下的语法分析算法还有递归下降语法分析算法,但是递归下降语法分析器相对有LL(1)语法分析器有很多缺点。 关于递归下降语法分析算法我这里不多说了。说一下LL(1)文法相对于递归下降算法的优点。


  • 速度快

  • 可自动化分析

  • 不需要回溯


在说LL(1)算法之前 我们必须要了解几个东西:


  • 文法

  • FIRST集

  • FOLLOW集

  • 消除左递归

  • 提取左公因


消除左递归,和提取左公因子。其实相对来说没有那么重要,这个部分可以手动转换。但是算法也在我之前的帖子中给出了。

 

如果说一点编译原理没有看过的话,那么这篇文章你看起来可能云里雾里的。

 

文法 是必须要所了解的点。


FIRST集FOLLOW集 是所有语法分析器都要用到的算法,非常非常重要。 如果说 FIRST集FOLLOW集 没有掌握好的话,那么所有的LL文法LR文法都是掌握不了的,更别说写出对应的算法了。

 

和大家简单介绍一下文法:


文法的全称是 上下文无关法, 他是一种规则用来约定一个语言的语法规则。其实正则表达式也是一种上下文无关法,但是不代表文法就是正则。相对于正则表达式,文法的表达能力更强,描述能力更强。

 

文法由四个部分组成:

  • 一个终结符号集合

  • 一个非终结符号集合

  • 一个产生式列表

  • 一个开始符号


本文不会将所有概念说到,因为太多了。

 

比如说一个算数表达式文法:

 

S -> E
E -> E + E
E -> E - E
E -> E / E
E -> E * E
E -> (E), num

 

在 -> 左部称为产生式头部(左部), 在 -> 右部的称为产生式体(右部)。
所有的产生式头 都是一个非终结符号。
所谓非终结符号就是 抽象的描述了一种规则。
而终结符号就是一个具体的事物。

 

在这个文法中 {S, E} 这两个是非终结符号, { +, -, *, /, num, (, ) }这些是终结符号。


但是上面的例子中说的文法并不是一个LL(1)文法。因为他是一个左递归文法。


E -> E + E 产生式头部和产生式体的第一个符号是相同的,就会导致LL(1)文法陷入一个死循环。LL(1)文法是一个文法最左推导过程,从左往右的推导。

 

当我们看到 S -> E的时候 我们会去推导 产生式体E


当我们看到 E -> E + E 的时候我们会去推导产生式 E + E, 但此时产生式体的第一个符号 E 让我们又陷入了要解析产生式E,然后就陷入一个死循环出不去了。(更详细的大家看书中所说的)


所以当我们看到 E -> E + E 的时候就要消除左递归。(可能还有间接左递归, 具体看我另外一篇文章)

 

在按照算数表达式优先级(括号优先级最大,其次是乘除法, 在是加减法)我们给出的文法是:


S -> E
E -> E + T | E - T | T
T -> T * F | T / F | F
F -> (E) | num

 

这里的 "|" 是用来分割产生式体的, 这些用 | 分开的产生式他们拥有相同的 左部。


下面的产生式是用我的程序消除左递归后的文法。


S -> E |
E -> TE
|T -> FT |
F -> (E) | num |
E
-> +TE | -TE| ε | T-> *FT| /FT | ε |

 

上文的图片中说了, LL(1)文法就是根据向前看1个输入就可以确定应用哪个产生式进行解析。


比如说 现在我们要推导E
:    他有3个产生式体: +TE | -TE| ε    FIRST(E) = {+, -, ε} 这是他的FIRST集。


当我们输入中的符号是 + 号时, 我们就选用+TE
这个产生式来推导, 是 - 号时选用-TE


但是我们发现这个E还可以推导出ε (空串), 也就是说 E是可以为空的。 那我们什么时候应用 E-> ε这个产生式? 此时我们就要查看什么终结符号可以跟在 E的后面也就是 FOLLOW(E) = { ), $ } 这两个符号。也就是说当遇到 ), $ 这两个终结符号时。我们就应用 E -> ε这个产生式。

 

举个简单的例子:

 

S -> ABC
A -> a | ε
B -> b
C -> c


这个文法有4个产生式: S 是文法的开始符号。


这个产生式要匹配一个 abc 或者 bc 的字符串, 也就是终结符a是可以不存在的, 因为非终结符A是可以推导出空串的。那我们看看什么时候应用这个产生式。 当非终结符A可以推导出空串的时候 我们就要获取FOLLOW(A)的值,此时可以跟在A后面的只有B,而FIRST(B)的值是b.就是说当A产生式遇到终结符b时那么就应用 A ->  ε这个产生式。


LL(1)是基于预测分析表生成的。


预测分析表的算法其实我上面已经说了,现在给出书中的定义:


LL(1)算法的伪代码:


这个伪代码其实很简单,不过我的程序中加上了生成语法树。可能略微复杂。

 

现在给出完整代码:


https://github.com/hixiaosan/cpp_dragon.git

 

Parser.h

#pragma once

#include "CFG.h"
#include "Lex.h"

// 语法分析基类
class Parser
{

public:
   Parser(CFG::CFG *cfg, Lex *lex);
   ~Parser();

protected:
   /// 获取FIRST集合
   std::set<std::string> First(CFG::GrammarSymbolic *symbolic);

   /// 获取FOLLOW集合
   std::set<std::string> Follow(std::string symbolic);

private:
   std::set<std::string> follow(std::string symbolic);

protected:
   CFG::CFG *cfg_;
   Lex *lex_;

private:
   std::set<std::string> follow_record_;
};


Parser.cpp

#include "Parser.h"



Parser::Parser(CFG::CFG *cfg, Lex *lex) : cfg_(cfg), lex_(lex)
{

}


Parser::~Parser()
{
}

// 获取FIRST集合, 文法必须是消除左递归后的文法 可以处理绝大多数文法,但不是所有文法,有一些特例。
std::set<std::string> Parser::First(CFG::GrammarSymbolic * symbolic)
{
   std::set<std::string> first_set;

   // 规则一 如果符号是一个终结符号,那么他的FIRST集合就是它自身
   if (symbolic->Type() == CFG::SYMBOLIC_TYPE_TERMINAL)
   {
       first_set.insert(symbolic->Name());

       return first_set;
   }

   // 规则二 如果一个符号是一个非终结符号(A)
   // (1) A -> XYZ 如果 X 可以推导出nil 那么就去查看Y是否可以推导出nil
   //              如果 Y 推导不出nil,那么把Y的First集合加入到A的First集合
   //                如果 Y 不能推导出nil,那么继续推导 Z 是否可以推导出nil,依次类推
   // (2) A -> XYZ 如果XYZ 都可以推导出 nil, 那么说明A这个产生式有可能就是nil, 这个时候我们就把nil加入到FIRST(A)中

   std::string current_symbolic_name = symbolic->Name();

   auto productions = cfg_->Productions();

   for (size_t i = 0; i < productions.size(); i++)
   {
       // 不匹配的产生式
       if (productions[i]->Header() != current_symbolic_name)
       {
           continue;
       }

       // 一个非终结符号有一个或者多个产生式体 要一一求出他的FIRST集
       for (size_t k = 0; k < productions[i]->Body().size(); k++)
       {
           auto body = productions[i]->Body()[k];
           bool has_nil = false;

           // 推导这个产生式体的所有FIRST集合
           for (size_t t = 0; t < body.size(); t++)
           {
               has_nil = false;
               auto fset = First(body[t]);

               for (auto terminal_sym : fset)
               {
                   if (terminal_sym == "ε") // 查看集合中是否包含空
                   {
                       has_nil = true;
                       continue;
                   }

                   // 插入到当前符号
                   first_set.insert(fset.begin(), fset.end());
               }

               // 如果当前符号不为空的话 则不需要继续推导产生式下面的符号
               if (has_nil == false)
               {
                   break;
               }
           }

           // 如果说到最后一个符号都可以推导出ε, 那么这个产生式就 可以为空
           if (has_nil == true)
           {
               first_set.insert("ε");
           }

       }

       break;
   }


   return first_set;
}

std::set<std::string> Parser::follow(std::string A)
{
   // 一个文法符号的FOLLOW集就是 可能出现在这个文法符号后面的终结符
   // 比如 S->ABaD, 那么FOLLOW(B)的值就是a。
   //                    FOLLOW(A)的值包含了FIRST(B)中除了ε以外的所有终结符,如果First(B)包含空的话。说明跟在B后面的终结符号就可以跟在A后面,这时我们要把FOLLOW(B)的值也添加到FOLLOW(A)中
   //                  因为D是文法符号S的最右符号,那么所有跟在S后面的符号必定跟在D后面。所以FOLLOW(S)所有的值都在FOLLOW(D)中
   //                     以下是书中的总结

   // 不断应用下面这两个规则,直到没有新的FOLLOW集 被加入
   // 规则一: FOLLOW(S)中加入$, S是文法开始符号
   // 规则二: A->CBY FOLLOW(B) 就是FIRST(Y)
   // 规则三: A->CB 或者 A->CBZ(Z可以推导出ε) 所有FOLLOW(A)的符号都在FOLLOW(B)

   std::set<std::string> follow_set;

   // 如果是文法的开始符号,那么加入$
   if (cfg_->StartSymbolic() == A)
   {
       follow_set.insert("$");
   }

   // 搜索所有包含 A 符号的产生式
   auto productions = cfg_->Productions();

   for (size_t i = 0; i < productions.size(); i++)
   {
       // 获取所有的产生式
       for (size_t t = 0; t < productions[i]->Body().size(); t++)
       {
           auto body = productions[i]->Body()[t];

           for (size_t k = 0; k < body.size(); k++)
           {
               if (A != body[k]->Name())
               {
                   continue;
               }

               // 第一种情况 符号在产生式的最末尾, 那么我们就要去获取产生式头部的FOLLOW集
               if (k == body.size() - 1)
               {
                   // 没有被FOLLOW过, 避免陷入死循环
                   if (follow_record_.end() == std::find(follow_record_.begin(), follow_record_.end(), productions[i]->Header()))
                   {
                       follow_record_.insert(productions[i]->Header());
                       auto fset = follow(productions[i]->Header());
                       follow_set.insert(fset.begin(), fset.end());
                   }
                   continue;
               }

               // 不是在最后一个符号 我们获取文法符号的下一个符号的First集合
               auto fset = First(body[k + 1]);

               bool has_nil = false;
               for (auto terminal_symbolic : fset)
               {
                   if (terminal_symbolic == "ε")
                   {
                       has_nil = true;
                       continue;
                   }

                   follow_set.insert(terminal_symbolic);
               }

               // 如果下一个First集合包含ε
               if (has_nil)
               {
                   follow_record_.insert(body[k + 1]->Name());
                   auto fset = follow(body[k + 1]->Name());
                   follow_set.insert(fset.begin(), fset.end());
               }


           }
       }
   }

   return follow_set;
}

std::set<std::string> Parser::Follow(std::string A)
{
   follow_record_.clear();
   follow_record_.insert(A);
   return follow(A);
}


LL1.h

#pragma once

#include "Parser.h"
#include <map>

struct ASTNode;

// 抽象语法树
struct AST
{

   ASTNode *root;
};

struct ASTNode
{

   CFG::GrammarSymbolic *symbolic; // 文法符号
   std::vector<ASTNode *> nodes;    // 子节点
};

// LL(1) 语法分析
class LL1 : Parser
{
public:
   LL1(CFG::CFG *cfg, Lex *lex);
   ~LL1();

private:
   void InitParser();

public:
   /// 语法分析
   AST Parse();

private:
   // LL(1) 预测分析表
   std::map<std::string, std::map<std::string, CFG::ProductionBody>> ll1_table_;
};


LL1.cpp

#include "LL1.h"
#include <stack>



LL1::LL1(CFG::CFG *cfg, Lex *lex) : Parser(cfg, lex)
{
   // 文法要移除左递归和提取左公因子
   cfg_->RemoveRecursive();
   cfg_->TakeLeft();

   InitParser();
}


LL1::~LL1()
{
}

void LL1::InitParser()
{
   // 生成预测分析表的目的就是让 LL(1) 文法, 向前看一个符号就可以确定使用非终结符的哪个产生式。
   // 比如:  A->cBD | bFA
   //         当我们开始推导非终结符 A 的时候, 我们向前看输入中的一个终结符号,
   //         如果终结符号是 c 我们就选择 A->cBD产生式来推导非终结符A。 如果终结符号是b那么我们就选择 A -> bFA来推导非终结符A。

   // 预测分析表有两个规则
   // 规则一: 产生式 A->B, 对于First(B)中的所有终结符号a, 把A->B这个产生式加入到 M[A, a]中。
   // 规则二: 产生式 A->B, 如果First(B)中包含nil串, 那么对Follow(A)的所有终结符号b, 把A->B这个产生式加入到 M[A, b]中。
   // 比如产生式:
   //        A->BC
   //        F->GAc
   //        B->a | ε
   //        C->f | ε
   //     首先我们获取 FIRST(BC)的所有终结符号集合 {a, f, ε}, 我们把A->B 添加到M[A, a], M[A, f]。
   //  其次我们发现 FIRST(BC)中是包含ε的, 那么我们就获取FOLLOW(A)的值. FOLLOW(A) => {c, $}, 那么我们就把 A->B 也添加到 M[A, c], M[A, $]中。
   auto products = cfg_->Productions();

   for (size_t i = 0; i < products.size(); i++)
   {
       auto pro = products[i]->Body();
       // 获取所有的产生式右部
       for (size_t k = 0; k < pro.size(); k++)
       {
           // 对于某一条产生式右部的所有符号
           // 比如 A -> BCD
           // 从左往右的顺序是 B-C-D
           // 首先推导 FIRST(B) 如果FIRST(B)不能推导出空串那么就把 FIRST(B)中的所有终结符a。 把当前处理的产生式加入到 M[A, a]
           //         FIRST(B) 如果可以推导出空串, 那么意味着 B 这个符号是可以不存在的,那么我们就要查看 FIRST(C) 集合。依次循环这个步骤。

           // -------------------
           // 如果说 FIRST(B) FIRST(C) FIRST(D) 都包含空串那么就说明了 整个产生式都是可以推导出空串的。
           // 比如说  B -> b | ε
           //         C -> c | ε
           //         D -> d | ε
           // BCD 都可以为空, 那么 A 就可以为空了。这个时候我们就要获取 FOLLOW(A)的值来确定应用当前的产生式
           bool has_nil = false;
           for (size_t t = 0; t < pro[k].size(); t++)
           {
               auto first_set = First(pro[k][t]);

               has_nil = false;

               for (auto terminal_symbolic : first_set)
               {
                   if (terminal_symbolic == "ε")
                   {
                       has_nil = true;
                       continue;
                   }

                   ll1_table_[products[i]->Header()][terminal_symbolic] = pro[k];
               }

               // 当前符号不能推导出空串那么就结束
               if (false == has_nil)
               {
                   break;
               }
           }

           // 产生式右部所有的符号都可以为空
           if (has_nil)
           {
               auto follow_set = Follow(products[i]->Header());

               for (auto terminal_symbolic : follow_set)
               {
                   ll1_table_[products[i]->Header()][terminal_symbolic] = pro[k];
               }
           }

       }


   }
}


AST LL1::Parse()
{
   AST ast;
   ast.root = new ASTNode;
   auto cur_node = ast.root;

   cur_node->symbolic = new CFG::GrammarSymbolic(cfg_->StartSymbolic(), CFG::SYMBOLIC_TYPE_N_TERMINAL);

   std::stack<std::string> ll1_stack;
   std::vector<std::vector<void *>> ast_stack; // 语法分析栈(递归栈)

   ll1_stack.push("$"); // 结束符号
   ll1_stack.push(cfg_->StartSymbolic()); // 文法开始符号

   // 进入下一层语法栈

   ast_stack.push_back(std::vector<void *>());
   // 栈中的两个局部变量
   ast_stack.back().push_back(0);
   ast_stack.back().push_back(cur_node);


   size_t stack_deep = 0;

   auto X = ll1_stack.top();
   auto input_token = lex_->FetchNext();
   if (NULL == input_token)
   {
       throw std::runtime_error("词法分析失败");
   }

   while (X != "$")
   {
       if (cfg_->IsTerminal(X))
       {
           if (X == input_token->Name())
           {
               ll1_stack.pop(); // 当前符号出栈

               input_token = lex_->FetchNext(); // 获取下一个输入符号

               if (NULL == input_token)
               {
                   throw std::runtime_error("词法分析失败");
               }
           }
           else if (X == "ε")
           {
               ll1_stack.pop(); // 当前符号出栈
           }
           else
           {
               throw std::runtime_error("语法分析错误");
           }

           do
           {
               if (ast_stack.size() <= 1)
               {
                   break;
               }

               // 索引右移动
               ast_stack.back()[0] = (void *)((int)ast_stack.back()[0] + 1);
               int idx = (int)ast_stack.back()[0];
               int parent_idx = (int)ast_stack[ast_stack.size() - 2][0];
               ASTNode *node = (ASTNode *)ast_stack[ast_stack.size() - 2][parent_idx + 1];

               if (node->nodes.size() == idx)
               {
                   ast_stack.pop_back(); // 类似于返回
                   continue;
               }
               break;
           } while (true);


       }
       else if (cfg_->IsNTerminal(X)) // 如果是非终结符号
       {
           auto iter = ll1_table_[X].find(input_token->Name());
           if (iter == ll1_table_[X].end())
           {
               throw std::runtime_error("语法分析错误");
           }

           ll1_stack.pop(); // 弹出当前符号
           // 对于当前非终结符 应用的产生式体
           auto product_body = ll1_table_[X][input_token->Name()];

           for (int i = product_body.size() - 1; i >= 0; i--)
           {
               ll1_stack.push(product_body[i]->Name());
           }

           int idx = (int)ast_stack.back()[0];
           ASTNode *node = (ASTNode *)ast_stack.back()[idx + 1];

           // 进入下一层语法栈
           ast_stack.push_back(std::vector<void *>());

           // 栈中的两个局部变量
           ast_stack.back().push_back(0);

           for (size_t i = 0; i < product_body.size(); i++)
           {
               auto new_node = new ASTNode;
               new_node->symbolic = product_body[i];

               node->nodes.push_back(new_node);
               ast_stack.back().push_back(new_node);
           }






           stack_deep++; // 栈深度添加
       }

       X = ll1_stack.top(); // 重新设置X的值
   }

   return ast;
}


main.cpp

#include <iostream>
#include "CFG.h"
#include <stdlib.h>
#include <stdio.h>
#include "Lex.h"
#include "LL1.h"
#include <memory>
#include <Windows.h>
#include <gdiplus.h>

using namespace Gdiplus;
#pragma comment (lib,"Gdiplus.lib")

using std::cin;
using std::cout;

void TestParse()
{
   // 产生式列表
   const char *products = "S -> E\n"
                          "E -> E + T | E - T | T\n"
                          "T -> T * F | T / F | F\n"
                          "F -> (E) | num";

   // 非终结符号集合
   std::set<std::string> n_terminal_set =  { "S", "E", "T", "F" };

   // 终结符号集合
   std::set<std::string> terminal_set = { "num", "+", "-", "*", "/", "(", ")" };

   try
   {
       CFG::CFG cfg(n_terminal_set, terminal_set, products, "S");
       std::cout << "消除左递归之前: " << std::endl << cfg << std::endl;
       std::cout << "消除左递归后: " << std::endl << cfg.RemoveRecursive();
   }
   catch (const std::exception &exp)
   {
       std::cout << exp.what() << std::endl;
   }


}

void TestFirst()
{

}

// 获取树的深度
int ASTDeep()
{
   return 0;
}


// 获取树的宽度
int ASTWidth(ASTNode *node)
{
   if (node->nodes.size() == 0)
   {
       node->width - 1;
       return 1;
   }

   int width = 0;
   for (auto n : node->nodes)
   {
       width += ASTWidth(n);
   }
   node->width = width;
   return width;
}

int GetEncoderClsid(const WCHAR* format, CLSID* pClsid)
{
   UINT  num = 0;          // number of image encoders
   UINT  size = 0;         // size of the image encoder array in bytes

   ImageCodecInfo* pImageCodecInfo = NULL;

   GetImageEncodersSize(&num, &size);
   if (size == 0)
       return -1;  // Failure

   pImageCodecInfo = (ImageCodecInfo*)(malloc(size));
   if (pImageCodecInfo == NULL)
       return -1;  // Failure

   GetImageEncoders(num, size, pImageCodecInfo);

   for (UINT j = 0; j < num; ++j)
   {
       if (wcscmp(pImageCodecInfo[j].MimeType, format) == 0)
       {
           *pClsid = pImageCodecInfo[j].Clsid;
           free(pImageCodecInfo);
           return j;  // Success
       }
   }

   free(pImageCodecInfo);
   return -1;  // Failure
}

const int kNodeWidth = 50;
const int kNodeHeight = 50;
const int space = 20;
const int kRadii = kNodeWidth / 2;
const int nBitmapW = 3000;
const int nBitmapH = 1080;

int AnsiToUnicode(LPWSTR wstrUnicode, LPCSTR szAnsi)
{
   DWORD dwMinSize = 0;
   dwMinSize = MultiByteToWideChar(CP_ACP, 0, szAnsi, -1, NULL, 0);
   if (0 == dwMinSize)
   {
       return 0;
   }
   MultiByteToWideChar(CP_ACP, 0, szAnsi, -1, wstrUnicode, dwMinSize);

   return dwMinSize;
}

int LeftWidth(ASTNode *node, int offset = 0)
{
   int left = offset;
   bool hasMiddle = node->nodes.size() % 2;
   for (size_t i = 0; i < node->nodes.size(); i++)
   {


       if (i < node->nodes.size() / 2) // 在左边
       {
           left = min(left, LeftWidth(node->nodes[i], offset - 1));

       }
       else if (i == node->nodes.size() / 2 && hasMiddle) { // 在中间
           LeftWidth(node->nodes[i], offset);
       }
       else { // 在右边
           left = min(left, LeftWidth(node->nodes[i], offset + 1));
       }
   }

   return left;
}

void MakeASTIMG(ASTNode *node, Gdiplus::Graphics &graphics, int center_x,  int deep = 0)
{
   FontFamily  fontFamily(L"Times New Roman");
   Font        font(&fontFamily, 18, FontStyleRegular, UnitPixel);
   int x = center_x - kRadii + kNodeWidth + space;


   Gdiplus::RectF       rectF(x , deep * 100, kNodeWidth, kNodeHeight);
   Gdiplus::SolidBrush  solidBrush(Color(255, 0, 0, 255));


   Pen      pen(Color::White, 1);
   graphics.DrawEllipse(&pen, rectF);

   Gdiplus::StringFormat sf;
   sf.SetAlignment(Gdiplus::StringAlignmentCenter);
   sf.SetLineAlignment(Gdiplus::StringAlignmentCenter);
   WCHAR wchar[100] = { 0 };
   AnsiToUnicode(wchar, node->symbolic->Name().c_str());

   graphics.DrawString(wchar, -1, &font, rectF, &sf, &solidBrush);

   if (node->nodes.size() == 1)
   {
       graphics.DrawLine(&pen, x + kRadii, deep * 100 + kNodeHeight, center_x + kNodeWidth + space, (deep + 1) * 100);


       MakeASTIMG(node->nodes[0], graphics, center_x, deep + 1);
       return;
   }

   int width = ASTWidth(node); // 当前节点宽度
   int sum_width = 0;
   bool lastInMid = false;
   bool hasMiddle = node->nodes.size() % 2;

   int left = abs(LeftWidth(node) * (kNodeWidth + space));
   center_x -= left;

   for (size_t i = 0; i < node->nodes.size(); i++)
   {
       int current_width = ASTWidth(node->nodes[i]);
       int cur_width = current_width * (kNodeWidth + space);
       int left = abs(LeftWidth(node->nodes[i])) * (kNodeWidth + space);
       int to_centor_x = center_x + (sum_width) + left;

       graphics.DrawLine(&pen, x + kRadii, deep * 100 + kNodeHeight, to_centor_x  + kNodeWidth + space, (deep + 1) * 100);


       MakeASTIMG(node->nodes[i], graphics, to_centor_x, deep + 1);

       sum_width += cur_width;
   }

}

// 生成语法树图片
void MakeASTIMG(ASTNode *node)
{
   ///// 生成图片太麻烦了.... 还是先打印出来树结构吧
   //for (int i = 0; i <= deep; ++i)
   //{
   //    std::cout << "\t";
   //}
   //auto str = node->symbolic->Name() == "ε" ? "@" : node->symbolic->Name();

   //std::cout << str << std::endl << std::endl;;

   //
   //
   //for (size_t i = 0; i < node->nodes.size(); i++)
   //{
   //    MakeASTIMG(node->nodes[i], deep + 1);
   //}

   // 节点的宽度 高度 和间隔


   int width = ASTWidth(node); // 树的宽度

   HDC hMemoryDC = CreateCompatibleDC(NULL);

   HBITMAP hBitMap = CreateCompatibleBitmap(hMemoryDC, nBitmapW, nBitmapH);

   SelectObject(hMemoryDC, hBitMap);

   Graphics graphics(hMemoryDC);

   Gdiplus::SolidBrush white(Color(255, 255, 255, 255));
   graphics.FillRectangle(&white, 0, 0, nBitmapW, nBitmapH);

   MakeASTIMG(node, graphics, nBitmapW / 2);

   // 生成图片
   BITMAP bm;
   GetObject(hBitMap, sizeof(BITMAP), &bm);
   WORD BitsPerPixel = bm.bmBitsPixel;

   using namespace Gdiplus;
   Bitmap* bitmap = Bitmap::FromHBITMAP(hBitMap, NULL);
   EncoderParameters encoderParameters;
   ULONG compression;
   CLSID clsid;

   if (BitsPerPixel == 1)
   {
       compression = EncoderValueCompressionCCITT4;
   }
   else
   {
       compression = EncoderValueCompressionLZW;
   }
   GetEncoderClsid(L"image/jpeg", &clsid);

   encoderParameters.Count = 1;
   encoderParameters.Parameter[0].Guid = EncoderCompression;
   encoderParameters.Parameter[0].Type = EncoderParameterValueTypeLong;
   encoderParameters.Parameter[0].NumberOfValues = 1;
   encoderParameters.Parameter[0].Value = &compression;

   bitmap->Save(L"1.jpeg", &clsid, &encoderParameters);
   delete bitmap;


}

void TestParseLL1()
{
   // 产生式列表
   const char *products = "S -> E\n"
       "E -> E + T | E - T | T\n"
       "T -> T * F | T / F | F\n"
       "F -> (E) | num";

   // 非终结符号集合
   std::set<std::string> n_terminal_set = { "S", "E", "T", "F" };

   // 终结符号集合
   std::set<std::string> terminal_set = { "num", "+", "-", "*", "/", "(", ")" };
   CFG::CFG cfg(n_terminal_set, terminal_set, products, "S");

   char line[255] = { 0 };
   cin.getline(line, sizeof(line));
   LL1 ll1(&cfg, new ExpLex(line));
   try
   {
       auto ast = ll1.Parse(); // 解析成功生成语法分析树
       MakeASTIMG(ast.root);
   }
   catch (std::exception &err)
   {
       std::cout << err.what() << std::endl;
   }


}

int main()
{
   GdiplusStartupInput gdiplusStartupInput;
   ULONG_PTR           gdiplusToken;
   GdiplusStartup(&gdiplusToken, &gdiplusStartupInput, NULL);
   //TestParse();
   TestParseLL1();
   system("pause");

   return 0;
}

当我们输入错误的表达式语法时就会报错:

 

当我们输入正确的语法时就会在程序运行目录生成一张 1.jpeg的图片。


 

其实多叉树生成这种图片的算法,大家有兴趣可以看一下。我修修改改花了一整天才实现的。



- End -


看雪ID:菜鸟级X               

https://bbs.pediy.com/user-453343.htm



本文由看雪论坛  菜鸟级X   原创

转载请注明来自看雪社区



热门图书推荐:

立即购买!



热门技术文章:        





公众号ID:ikanxue

官方微博:看雪安全

商务合作:wsc@kanxue.com


点击下方“阅读原文”

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存