为递归下降解析器制作 shell 文法

Question

对于一个学校项目，我们被分配编写一个 mini-shell：一个功能有限的小型 shell，用 C 语言编写。

我被递归下降解析器的明显简单所吸引，并决定手工编写这样的解析器。

shell 应该处理（内置等）：

基本重定向 <，> 与 here-doc <<。
管道|
逻辑 OR || 和逻辑 AND && 带括号 ( )（我们不会像 bash 那样分配并执行 subshell 在括号中，它们像在数学中一样用于优先级）。

我已经编写并实现了这个语法，仅用于重定向和管道，没有任何问题（BNF 表示法）：

<pipeline>          ::=     <simple_command>    '|' <pipeline>
                      |     <simple_command>    'ε'

<simple_command>    ::=     <io_list>           <word><cmd_suffix>
                      |     <io_list>           <word>
                      |     <io_list>
                      |     <word>              <cmd_suffix>
                      |     <word>

<io_list>           ::=     <io_redirect>       <io_list>
                      |     <io_redirect>

<cmd_suffix>        ::=     <io_list>           <cmd_suffix>
                      |     <io_list>
                      |     <word>              <cmd_suffix>
                      |     <word>

<io_redirect>       ::=     '<'             <word>
                      |     '>'             <word>
                      |     '>>'            <word>
                      |     '<<'            <word>

然后我尝试将此语法用于 && 和 || 以及 ( ) :

<complete_command>  ::=     <and_or>        'ε'

<and_or>            ::=     <pipeline>      '&&'        <and_or>
                      |     <pipeline>      '||'        <and_or>
                      |     <pipeline>

<command>           ::=     <simple_command>
                      |     '('     <and_or>    ')'

<pipeline>          ::=     <command>           '|'         <pipeline>
                      |     <command>

<simple_command>    ::=     <io_list>       <word>          <cmd_suffix>
                      |     <io_list>       <word>
                      |     <io_list>
                      |     <word>          <cmd_suffix>
                      |     <word>

<io_list>           ::=     <io_redirect>       <io_list>
                      |     <io_redirect>

<cmd_suffix>        ::=     <io_list>           <cmd_suffix>
                      |     <io_list>
                      |     <word>              <cmd_suffix>
                      |     <word>

<io_redirect>       ::=     '<'             <word>
                      |     '>'             <word>
                      |     '>>'            <word>
                      |     '<<'            <word>

但是在测试的时候才发现：

这种语法导致大量递归。
此语法不为 && 和 || 运算符提供左结合性。

你有没有想过写一个处理左结合性的语法？这似乎是递归下降解析器的一个缺陷..（或者只有我没有想法）。

Answer 1

left-associative 运算符的 BNF 语法需要是 left-recursive，这似乎消除了递归下降解析。显然情况并非如此，因为许多表达式解析器都是以递归下降风格的某种变体编写的（尽管必须说 bottom-up 解析是表达式语法更自然的匹配）。

关键是递归下降解析器可以处理不限于简单 BNF 的语法规范。特别是，RD 解析器可以通过将其转换为 while 循环来简单地处理贪婪重复而无需递归；这有效地为您提供了一个术语列表而不是 right-leaning 成对树，并且可以减少该列表 left-to-right 产生 left-associative 解析。

你最终可能会得到一个看起来像这样的语法。这里，{ X } 表示“X 的任何数字（包括 0）”，( X | Y ) 表示“X 或 Y”。

<complete_cmd> ::=  <and_or> <newline>
<and_or>       ::=  <pipeline> { ('&&' | '||') <pipeline> }        
<pipeline>     ::=  <command> { '|' <command> }
<command>      ::=  <simple_cmd> | '(' <and_or> ')'
<simple_cmd>   ::=  { <redirect> } <word> { ( <redirect> | <word> ) }
<redirect>     ::=  ( '<' | '>' | '<<' | '>>' ) <word>

{ X } 结构是用 while 循环实现的：

AST* parse_and_or(Scanner* scanner) {
  AST* result = parse_pipeline(scanner);
  while (1) {
    switch(token_peek(scanner)) {
      default:
        return result;
      case T_AND_IF:
      case T_OR_IF: {
        enum Token token = token_get(scanner);
        AST* pipeline = parse_pipeline(scanner);
        result = make_andor(token, result, pipeline);
      }
    }
  }
}

如果您想使用运算符优先级，可以在使用“优先级攀登”的递归下降解析器中实现，其中递归调用包括优先级阈值和 returns 当找到运算符时'满足那个门槛。例如，参见 pseudocode in the Wikipedia article on operator precedence。但是对于简单的表达式语法，只写出递归规则可能更容易，一次一个优先级别。

为递归下降解析器制作 shell 文法

Making a shell grammar for a recursive descent parser

c

shell

parsing

recursion