3

我很难弄清楚从哪里开始这个问题。问题是用字母表为正则表达式的语言创建一个语法{ ‘a’, ‘b’, ‘c’, ‘d’, ‘|’, ‘*’, ‘(‘, ‘)’ }。假设有 1 行输入（单个字符串）并且没有空格。空字符串是无效的，它应该正确地捕获运算符的优先级，从低到高是联合（'|'）、连接和 kleene（' *'）。开始为此编写语法的最佳方法是什么？任何投入将不胜感激。

不寻找答案，只是不知道如何开始。到目前为止，我有类似的东西： 

S -> S'('S')'S  
   | A  
A -> AA  
   | A'*'  
   | T  
T -> T'|'T  
   | X  
X -> 'a'  
   | 'b'  
   | 'c'  
   | 'd'

但我不确定我是否走在正确的轨道上。

编辑：在做了更多的工作之后，这是我得出的结论： 

START -> EXPRESSION  
EXPRESSION -> EXPRESSION'|'EXPRESSION  
EXPRESSION -> PARENTHETICAL'*'  
EXPRESSION -> PARENTHETICAL  
EXPRESSION -> EXPRESSION PARENTHETICAL  
EXPRESSION -> PARENTHETICAL EXPRESSION  
EXPRESSION -> EXPRESSION PARENTHETICAL EXPRESSION  
EXPRESSION -> REPEAT  
PARENTHETICAL -> PARENTHETICAL'*'  
PARENTHETICAL -> '('EXPRESSION')'  
REPEAT -> REPEAT REPEAT
REPEAT -> TERMINAL'*'  
REPEAT -> TERMINAL  
TERMINAL -> TERMINAL'*'  
TERMINAL -> 'a'  
TERMINAL -> 'b'  
TERMINAL -> 'c'  
TERMINAL -> 'd'

这也可以写成： 

S -> E  
E -> E'|'E  
E -> P'*'  
E -> P  
E -> E P  
E -> P E 
E -> E P E  
E -> R  
P -> P'*'  
P -> '('E')'  
R -> R R
R -> T'*'  
R -> T  
T -> T'*'  
T -> 'a'  
T -> 'b'  
T -> 'c'  
T -> 'd'

我相当肯定这是正确的，我用一堆不同的测试输入仔细检查了它。任何确认将不胜感激。

4

2 回答 2

2

这只是一个迭代的问题。我总是喜欢从规则开始Start-> NonTerminal，只是给自己半个机会学习常规语法。我相信嵌套括号会将我们简化为上下文无关语法，但这很好。我发现它使这一步更容易。然后，您必须从 LOWEST 优先级运算符开始。在你的情况下，括号和联合。所以，最初：

Start -> Expression
Expression -> Expression|Expression
Expression -> (Expression)

请注意，我避开了正常的“|” 符号，因为它是字母表中的符号之一。这样可以避免混淆。然后，我们可以添加下一个运算符，连接，以及一组生成重复的规则。

Start -> Expression
Expression -> Expression|Expression
Expression -> (Expression)

Expression -> Repeat
Repeat -> RepeatRepeat
Repeat -> Terminal
Terminal -> a
Terminal -> b
Terminal -> c
Terminal -> d

然后，剩下的就是添加 Kleene Star 作为最低优先级运算符：

Start -> Expression
Expression -> Expression|Expression
Expression -> (Expression)

Expression -> Repeat
Repeat -> RepeatRepeat
Repeat -> Terminal
Terminal -> a
Terminal -> b
Terminal -> c
Terminal -> d

Repeat -> Terminal*
Expression -> (Expression)*

我们有一个语法，可以从所需的字母表中生成所有非空的正则表达式。在更传统的变量表示法中，它可能如下所示：

S -> E
E -> E|E
E -> (E)
E -> (E)*
E -> R
R -> RR
R -> T*
R -> T
T -> a
T -> b
T -> c
T -> d

有一个语法我很确定它。希望有人会检查我的工作，因为我已经有几年没有写正式的语法了。

编辑：

作为上述双重检查的结果，有人指出连接表达式和括号表达式不起作用。但是，我们可以添加它。第一步是添加一个新规则并进行Expression -> Parenthetical更改Expression -> (Expression)，然后，将它们连接起来的几个快速规则导致规则集：Expression -> (Expression)*Parenthetical -> (Expression)Parenthetical -> (Expression)*

Start -> Expression
Expression -> Expression|Expression
Expression -> Parenthetical

Parenthetical -> (Expression)
Parenthetical -> (Expression)*

Expression -> Expression Parenthetical
Expression -> Parenthetical Expression
Expression -> Expression Parenthetical Expression

Expression -> Repeat
Repeat -> Repeat Repeat
Repeat -> Terminal
Terminal -> a
Terminal -> b
Terminal -> c
Terminal -> d

Repeat -> Terminal*
于 2013-03-22T17:48:53.580 回答
-2

编译器新手很难理解的是，只能够解析有效输入的语法是无用的。

一个好的语法必须反映输入的层次结构，以便我们可以将语义附加到它。

这都是关于意义的。

也就是说，Grako有一个正则表达式到 CFG 的翻译器作为其唯一的示例项目。

于 2013-03-23T17:33:30.033 回答