Манипуляция строк в C - PullRequest
2 голосов
/ 17 мая 2010

Я помогаю своему племяннику за домашнее задание в лаборатории C, это задание по обработке строк и применение алгоритма Вана.

Вот BNF-представление для ввода.

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

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

Как лучше всего обрабатывать и анализировать этот тип ввода в C? Как я могу разобрать эту структуру без использования struct? Заранее спасибо.

Ответы [ 2 ]

3 голосов
/ 17 мая 2010

Самый простой подход - сделать каждое правило (или «производство») функцией. Это называется синтаксическим анализатором "рекурсивного спуска".

Напишите две подпрограммы, которые будут смотреть и получать следующий символ.

Это даст вам некоторый код, который выглядит примерно так (в псевдокоде):

// <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

и т. Д. Для каждого правила.

Общая идея:

  • каждое правило является функцией
  • в определенные моменты функция заглядывает вперед, чтобы увидеть, что делать. например, формула () проверяет, является ли первый символ знаком минус.
0 голосов
/ 17 мая 2010

Поскольку у вас уже есть ваш BNF, самый простой способ для анализа этого вида ввода будет использовать генератор анализатора. Но из-за того, что это домашнее задание, я не уверен, что использование генератора разрешено.

Тем не менее, вы также можете использовать рукописный парсер. Просто выполните поиск парсеров рекурсивного спуска ...

...