2

我需要解析一个如下所示的代码块：

* Block
| Line 1
| Line 2
| ...

这很容易做到：

block : head lines;
head  : '*' line;
lines : lines '|' line
      | '|' line
      ;

现在我想知道，如何添加嵌套块，例如：

* Block
| Line 1
| * Subblock
| | Line 1.1
| | ...
| Line 2
| ...

这可以表达为LALR语法吗？

当然，我可以解析顶级块，然后再次运行我的解析器来处理这些顶级块中的每一个。但是，我只是在学习这个主题，所以避免这种方法对我来说很有趣。

4

2 回答 2

3

嵌套块语言不是上下文无关的 [注 2]，因此不能用 LALR(k) 解析器解析。

|然而，嵌套括号语言当然是上下文无关的，通过替换词法扫描器中的初始序列，将输入转换为括号形式相对容易。转换很简单：

  • 当|s 的初始序列比上一行长时，插入一个BEGIN_BLOCK. （初始序列必须恰好|长一个；否则可能是语法错误。）

  • 当|s 的初始序列比前一行短时，插入足够END_BLOCK的 s 以使预期长度达到正确值。

  • |s 本身不会传递给解析器。

这与用于解析布局感知语言（如 Python 和 Haskell）的INDENT/策略非常相似。DEDENT主要区别在于这里我们不需要一堆缩进级别。

转换完成后，语法将如下所示：

content: /* empty */
       | content line
       | content block
block  : head BEGIN_BLOCK content END_BLOCK
       | head
head   : '*' line

一个 flex 实现的大致轮廓是这样的：（见下面的注 1）。

%x INDENT CONTENT
%%
  static int depth = 0, new_depth = 0;
  /* Handle pending END_BLOCKs */
  send_end:
    if (new_depth < depth) {
      --depth;
      return END_BLOCK;
  }
^"|"[[:blank:]]*   { new_depth = 1; BEGIN(INDENT); }
^.                 { new_depth = 0; yyless(0); BEGIN(CONTENT);
                     goto send_end; }
^\n                /* Ignore blank lines */
<INDENT>{
  "|"[[:blank:]]*  ++new_depth;
  .                { yyless(0); BEGIN(CONTENT);
                     if (new_depth > depth) {
                       ++depth;
                       if (new_depth > depth) { /* Report syntax error */ }
                       return BEGIN_BLOCK;
                     } else goto send_end;
                   }
  \n               BEGIN(INITIAL); /* Maybe you care about this blank line? */
}
  /* Put whatever you use here to lexically scan the lines */
<CONTENT>{
  \n               BEGIN(INITIAL);
}

笔记：

  1. 不是每个人都会对此感到满意，goto但它可以节省一些代码重复。depth状态变量 (和new_depth) 是局部变量这一事实static使得词法分析器不可重入和不可重新启动（发生错误后）。这仅对玩具代码有用；对于任何真实的东西，您应该使词法扫描器可重入并将状态变量放入extra数据结构中。

  2. 术语“上下文无关”和“上下文敏感”是语法的技术描述，因此有点误导。基于单词似乎意味着什么的直觉通常是错误的。上下文敏感性的一个非常常见的来源是一种语言，其中有效性取决于相同非终结符的两个不同派生产生相同的标记序列。（假设非终结符可以派生多个标记序列；否则，可以消除非终结符。）

    在普通编程语言中有很多这种上下文敏感的例子。通常，语法将允许这些结构，并且稍后将在某些语义分析阶段执行检查。其中包括声明标识符的要求（IDENTIFIER产生相同字符串的两个派生）或使用正确数量的参数调用函数的要求（这里只需要非终结符的派生长度匹配，但这足以触发上下文敏感性）。

    在这种情况下，要求是可能bar-prefix在连续行中调用的两个实例产生相同的|s 字符串。在这种情况下，由于效果确实是句法的，因此推迟到稍后的语义分析会破坏解析点。上下文敏感性的其他例子是“句法”还是“语义”是一个争论，它产生了惊人的热量，却没有对讨论产生太多影响。

于 2016-03-03T18:00:08.503 回答
0

如果你写一个明确的块结束标记，事情会变得更清楚：

*Block{
  |Line 1
  *SubBlock{
     | line 1.1
     | line 1.2
  }
  |Line 2
  |...
}

语法变成：

block : '*' ID '{' lines '}'
lines : lines  '|' line
      | lines  block
      |
于 2016-03-03T12:20:40.240 回答