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

为什么学习编译原理

因为前一段时间一直在研究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

官方微博：看雪安全

商务合作：[e-mail]

↙点击下方“阅读原文”