解析每行以特定符号开头的块

Question

我需要解析一段代码，如下所示：

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

很容易做到：

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

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

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

这可以用 LALR 语法表示吗？

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

Answer 1

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

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

语法变为：

block : '*' ID '{' lines '}'
lines : lines  '|' line
      | lines  block
      |

Answer 2

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

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

当|的初始序列比上一行长时，插入一个BEGIN_BLOCK。（初始序列必须恰好长 |；否则可能是语法错误。）
当 | 的初始序列比上一行短时，插入足够的 END_BLOCK 以使预期长度达到正确的值。
|本身不会传递给解析器。

这与用于解析 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);
}

备注：

并不是每个人都会对 goto 感到满意，但它可以节省一些代码重复。状态变量（depth 和 new_depth）是局部 static 变量这一事实使得词法分析器不可重入且不可重启（在出错后）。这只对玩具代码有用；对于任何真实的东西，您应该使词法扫描器可重入并将状态变量放入 extra 数据结构中。
术语 "context-free" 和 "context-sensitive" 是语法的技术描述，因此有点误导。基于字面意思的直觉往往是错误的。上下文敏感性的一个非常常见的来源是一种语言，其中有效性取决于同一非终端的两个不同派生产生相同的标记序列。（假设非终结符可以推导出不止一个token序列，否则非终结符可以被剔除。）

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

在这种情况下，要求是连续行中可能称为 bar-prefix 的两个实例产生相同的 | 字符串。在这种情况下，由于效果实际上是句法的，推迟到以后的语义分析会破坏分析的意义。上下文敏感的其他示例是 "syntactic" 还是 "semantic" 是一场争论，它产生了惊人的热量，却没有给讨论带来太多启发。

解析每行以特定符号开头的块

Parse a block where each line starts with a specific symbol

parsing

yacc

lalr

备注：