4

I am learning parsing, bison & lex. I am looking for a clear & complete tutorial/example that demonstrates all of:

  1. C++ (not C) Abstract Syntax Tree.
  2. Re-entrant lexer.
  3. Re-entrant parser.
  4. Reading from a string (vs. from file) would be nice as well.

I have found multiple examples and tutorials, but each typically meets only few of the above requirements. So far my best tutorial is from Chapter 3-2 in the Oreilly book by John Levine - it has AST; all C though, meets only Re_1 above. I welcome recommendations for nice examples / tutorials, real life open source projects. For example I saw MySql .yy file - looks well written, but too big/complex for beginner like me.

4

2 回答 2

4

最后我结合了几个例子来得到我想要的。前两个例子来自 John Levine 的关于 bison&flex 的书（第 2 版），ISBN-10: 0596155972。另一个来自 phpcompiler 网站，不幸的是，截至 2017 年 2 月 28 日，该网站已不存在。我将链接留在这里，以防网站存档在某处：www.phpcompiler.org/articles/reentrantparser.html

谢谢 Adrien，这是一个存档版本（截至 2017 年 3 月 2 日的作品）：

http://web.archive.org/web/20120520150851/http://www.phpcompiler.org/articles/reentrantparser.html

于 2012-06-14T00:30:27.110 回答
1

首先我想说的是，C++ 语法对于 Lex/Bison 来说太复杂了。这里的问题主要在于语法冲突。不可能编写没有它们的 C++ 语法。C++ 标准明确说明了这一点，并包含一些关于如何解决它们的指南。

没有解决语法冲突的通用解决方案。特别是 C++ 的语法冲突解决需要有关已定义标识符的详细知识。这意味着您需要拥有更大的 C++ 前端部分。仅有语法是不够的。

尽管如此，构建 AST 是可能的。看一个小示例程序。

class HashEntry
{
private:

      int key;
      int value;

public:

      HashEntry(int key, int value)
      {
            this->key = key;
            this->value = value;
      }

      int getKey() { return key; }

      int getValue() { return value; }
};

const int TABLE_SIZE = 128;

class HashMap
{
private:

      HashEntry **table;

public:

      HashMap()
      {
            table = new HashEntry*[TABLE_SIZE];

            for (int i = 0; i < TABLE_SIZE; i++)
                  table[i] = NULL;
      }

      int get(int key)
      {
            int hash = (key % TABLE_SIZE);

            while (table[hash] != NULL && table[hash]->getKey() != key)
                  hash = (hash + 1) % TABLE_SIZE;

            if (table[hash] == NULL)
                  return -1;
            else
                  return table[hash]->getValue();
      }

      void put(int key, int value)
      {
            int hash = (key % TABLE_SIZE);

            while (table[hash] != NULL && table[hash]->getKey() != key)
                  hash = (hash + 1) % TABLE_SIZE;

            if (table[hash] != NULL)
                  delete table[hash];

            table[hash] = new HashEntry(key, value);
      }     

      ~HashMap()
      {
            for (int i = 0; i < TABLE_SIZE; i++)
                  if (table[i] != NULL)
                        delete table[i];

            delete[] table;
      }
};

这是该程序的 AST： 在此处输入图像描述

这棵树被严重缩小了。叶子上的黄色圆圈（非常小）是终端符号，中间的绿色圆圈是非终端。中心的粉红色圆圈是 TranslationUnit。这棵树有 2009 个节点。

于 2012-06-14T00:03:05.740 回答