2

我正在帮助我的侄子完成他的 C 实验室作业，这是一个字符串操作作业并应用了 Wang 的算法。

这是输入的 BNF 表示。

<s> ::= <l> # <r>

<l> ::= <list>| ε
<r> ::= <list>| ε
<list> ::= <f>|<f> , <list>
<f> ::= <letter>| - <f>| (<f><op><f>)
<op> ::= & | | | >
<letter> ::= A |... | Z

在 C 中处理和解析这种输入的最佳实践是什么？如何在不使用的情况下解析此结构struct？提前致谢。

4

2 回答 2

3

最直接的方法是使每个规则（或“生产”）成为一个函数。这称为“递归下降”解析器。

编写两个例程来查看并获取下一个字符。

这将为您提供一些看起来像这样的代码（在伪代码中）：

// <sequent> ::= <lhs> # <rhs>
sequent()
    lhs()
    if peekchar() != '#' then error
    else poundsign = nextchar()
    rhs()


// <lhs> ::= <formulalist>| ε
lhs()
    if peekchar() == EOF
        return
    else
       formula()

// <rhs> ::= <formulalist>| ε
rhs()
    if peekchar() == EOF
        return
    else
       formulalist()

// <formulalist> ::= <formula>|<formula> , <formulalist>
formulalist()
   formula()
   if peekchar() is ','
       comma = nextchar()
       return formulalist()

// <formula> ::= <letter>| - <formula>| (<formula><infixop><formula>)
formula()
    next = peekchar()
    if next in A..Z
        letter
    else if next is -
        minus_sign = nextchar()
        return formula()
    else
        formula()
        infixop()
        formula()

// <infixop> ::= & | | | >
infixop()
    c = nextchar()
    if c not in &,|,> then error

// <letter> ::= A | B | ... | Z
letter()
    c = nextchar()
    if c not A..Z then error

等等，对于每个规则。

总体思路：

  • 每个规则都是一个函数
  • 在某些时候，该功能会向前看，看看要做什么。例如，formula() 检查第一个字符是否为减号。
于 2010-05-17T09:16:32.817 回答
0

由于您已经拥有 BNF，解析此类输入的最简单方法是使用解析器生成器。但由于这是家庭作业，我不确定是否允许使用发电机。

不过，您也可以使用手写解析器。只需搜索递归下降解析器...

于 2010-05-17T09:15:55.193 回答