java - 这些表达式的解析器语法

Question

我正在尝试提出一个简单的 EBNF 语法来解析以下表达式示例:(“->”不是输入的一部分)。 'a'、'b' 'c' 是仅包含字母的多字符单词。

-> a
-> (a)
-> (a | b | c)
-> (a (b | c | d))
-> (a (b | (c | d)) )
-> (a (
     b (
        c x
      | d (e | f)
      )
    )
  )

我尝试提出几种语法(在 Antlr 中)，但它们都在某些情况下崩溃，这就是我现在所拥有的，任何帮助将不胜感激。

term:   '(' WORD+ options_list ')' 
    |   '(' WORD+ ('|' term)* ')'
    |   WORD+
    ;

options_list:   '(' term ('|' term)* ')' 
    ;
}

WORD    :   ('a'..'z')+ 
    ;

编辑1:基本上我试图从语法中创建一个单词的分层树，例如在最后一种情况下，树看起来像这样

     [a]
      |
     [b]
     / \
 [c,x]  [d]
        /  \
       [e]  [f] 

出于不同的原因，我不想依赖 Antlr 或 JavaCC 自动生成解析器，我想编写自己的简单递归下降解析器，以便做到这一点，我首先想出一个有效的语法这适用于所有情况，那么从中实现起来就足够简单了。

编辑2:经过一些工作后，我得到了这个似乎适用于

term:   WORD term?
    |   '(' term ('|' term)* ')'
    ;


WORD    :   ('a'..'z')+ 
    ;

Answer 1

以下语法似乎可以解析您提供的所有示例。

term        : WORD+
            | '(' alt_term ')'
            ;

alt_term    : app_term
            | app_term '|' alt_term
            | app_term '|' '(' alt_term ')'
            ;

app_term    : WORD+
            | WORD+ '(' alt_term ')'
            ;

WORD        : ('a'..'z')+ 
            ;

我在AntlrWorks中测试了它，并且您的所有示例都已解析。我刚刚在空格上添加了 EOF 识别和 skip。

具体案例分析:

1. 一个

   1.1。 术语 (1)

2. (a)

   2.1。 术语 (2)

   2.2。 alt_term (1)

   2.3。 app_term (1)

3. (a | b | c)

   3.1。 术语 (2)

   3.2。 alt_term (2)

   3.3。 app_term (1)

   3.4。 alt_term (2)

   3.5。 app_term (1)

   3.6。 alt_term (1)

   3.7。 app_term (1)

4. (a (b | c | d))

   4.1。 术语 (2)

   4.2。 alt_term (1)

   4.3。 app_term (2)

   4.4。 alt_term (2)

   4.5。 app_term (1)

   4.6。 alt_term (2)

   4.7。 app_term (1)

   4.8。 alt_term (1)

   4.9。 app_term (1)

5. (a (b | (c | d)) )

   5.1。 术语 (2)

   5.2。 alt_term (1)

   5.3。 app_term (2)

   5.4。 alt_term (3)

   5.5。 app_term (1)

   5.6。 alt_term (2)

   5.7。 app_term (1)

   5.8。 alt_term (1)

   5.9。 app_term (1)

6. (a (b (c x | d (e | f))))

   6.1。 术语 (2)

   6.2。 alt_term (1)

   6.3。 app_term (2)

   6.4。 alt_term (1)

   6.5。 app_term (2)

   6.6。 alt_term (2)

   6.7。 app_term (1)

   6.8。 alt_term (1)

   6.9。 app_term (2)

   6.10。 alt_term (2)

   6.11。 app_term (1)

   6.12。 alt_term (1)

   6.13。 app_term (1)