如何在 CFG 中定义重复元素？

Question

我正在制作一个从文件加载 cfg 并使用它来将编程语言加载到语法树中的程序。

在上下文无关语法中定义标识符的正确方法是什么。现在，我有这样的格式：

IdentifierStart => $l$ | _; 
IdentifierChar => "$l$$IdentifierChar$" | "_$IdentifierChar$" | "$i$$IdentifierChar$" | $e$;
Identifier => "$IdentifierStart$$IdentifierChar$" $w$;

格式：

$l$ = any letter 
$e$ = epsilon
$i$ = any integer
$o$ = any operator
$n$ = new line
$w$ = whitespace
$a$ = any atom
Quotes mean the whitespace needs to match the inside of the quotes

虽然这确实有效，但效率低下，因为当每个字母都可以合理地彼此相邻列出时，它会创建一棵深树。例如， Pragma => $n$ "#direct" $w$ $String$; 规则：

IdentifierStart => $l$ | _;
IdentifierChar => "$l$$IdentifierChar$" | "_$IdentifierChar$" | "$i$$IdentifierChar$" | $e$;
Identifier => "$IdentifierStart$$IdentifierChar$";

Symbol => $l$ | $i$ | $o$ | $$Identifier$$;
Def => $Symbol$ $Def$ | $Symbol$ | "Def";
Assignment => $Def$ \| $Assignment$ | $Def$;
Definition => $Identifier$ "=>" $Assignment$\;;

创建以下树（其中每个 space 代表树中的一个级别）：

Definition:Pragma => $n$ "#pragma" $w$ $String$;
  Identifier:Pragma
   IdentifierStart:P
    Terminal:P
   IdentifierChar:ragma
    Terminal:r
    IdentifierChar:agma
     Terminal:a
     IdentifierChar:gma
      Terminal:g
      IdentifierChar:ma
       Terminal:m
       IdentifierChar:a
        Terminal:a
  Terminal:=
  Terminal:>
  Assignment:$n$ "#direct" $w$ $String$
...

虽然这在标识符的情况下很好，但当我意识到我必须以相同的递归方式定义文件格式时，我注意到存在问题：

File => $ValidDirective$ $File$;
ValidDirective => $Comment$ | $Include$ | $Define$ | $Undef$ | $IfPart$ | $Error$ | $Pragma$ | $String$;

文件的每个元素都将存储在前一个元素的子树中！我不认为这是可以接受的，因为在一个有数百万行的程序中，这将是非常低效的。

有什么方法可以解决这个问题，同时保持 CFG 的惯例？

Answer 1

真正的 CFG 确实通过递归定义了重复，这导致了您观察到的嵌套解析树。

编程语言通常会使用正则表达式（或类似的东西）来定义标识符等符号的语法。在那种情况下，解析标识符将产生单个标记，而不是树，这可能会回答您对效率低下的担忧。

但是，该方法不适用于更高级别的重复结构，例如StatementList 或 ArgumentList：对于这些，正则表达式是不够的，您至少需要 'powerful' 作为 CFG。目前还不清楚您是否认为将 StatementList 或 ArgumentList 存储为深度嵌套的树是低效的。

如果您不得不使用真正的 CFG，并且您无法控制在解析过程中创建的数据结构，您可以运行一个 post-process 转换将递归结构转化为非递归结构，但是你可能会发现效率提升并没有那么多。

不过，大多数编程语言语法并不局限于纯 CFG。

如何在 CFG 中定义重复元素？

How can I define repeating elements in CFG?

grammar