Как бороться с перекрывающимися группами символов в разных лексемах в грамматике EBNF? - PullRequest
2 голосов
/ 15 июня 2010

Я использую грамматику LL (k) EBNF для анализа потока символов.Мне нужны три разных типа токенов:

CHARACTERS

  letter = 'A'..'Z' + 'a'..'z' .
  digit = "0123456789" .
  messageChar = '\u0020'..'\u007e' - ' ' - '(' - ')' .

TOKENS

  num = ['-'] digit { digit } [ '.' digit { digit } ] .
  ident = letter { letter | digit | '_' } .
  message = messageChar { messageChar } .

Первые два объявления токенов подходят, потому что они не имеют общих символов.

Однако третий, message, этоневерно, поскольку возможно, что некоторые строки могут быть как num, так и message (например, "123"), а другие строки могут быть как ident, так и message (например, "Hello").Следовательно, токенизатор не может правильно различать.

Другой пример - это различие между целыми числами и действительными числами.Если вам не требуется, чтобы все действительные числа имели хотя бы одно десятичное число (то есть 1 нужно было бы закодировать как 1,0, что для меня не вариант), то я не могу получить поддержку в грамматике для различий между этими двумя числовымитипы.Я должен был пойти на все значения, выраженные в виде действительных значений и сделать проверку после точки.Это хорошо, но неоптимально.Моя настоящая проблема с токеном message.Я не могу найти обходной путь для этого.

Итак, вопрос в том, могу ли я сделать это с грамматикой LL (k) EBNF?Я использую CoCo / R для генерации синтаксического анализатора и сканера.

Если я не могу сделать это с LL (k) EBNF, то какие еще варианты я мог бы рассмотреть?

РЕДАКТИРОВАТЬ Это вывод, который я получаю из CoCo / R:

Coco/R (Apr 23, 2010)
Tokens double and message cannot be distinguished
Tokens ident and message cannot be distinguished
...
9 errors detected

Ответы [ 3 ]

3 голосов
/ 24 июня 2010

Попробуйте это:

CHARACTERS

    letter = 'A'..'Z' + 'a'..'z' .
    digit = "0123456789" .
    messageChar = '\u0020'..'\u007e' - ' ' - '(' - ')'  .

TOKENS

    double = ['-'] digit { digit } [ '.' digit { digit } ] .
    ident = letter { letter | digit | '_' } .
    message = messageChar { messageChar } CONTEXT (")") .

О, я должен указать, что '\u0020' - это пространство Юникода, которое вы впоследствии удаляете с помощью "- ' '". О, и вы можете использовать CONTEXT (')'), если вам не нужно более одного персонажа. В вашем случае это не работает, так как все вышеперечисленные токены могут появляться до ')'.

FWIW: CONTEXT не использует вложенную последовательность, вы все равно должны использовать ее в своем производстве.

EDIT:

Хорошо, похоже, это работает. На самом деле, я имею в виду это время:)

CHARACTERS
    letter = 'A'..'Z' + 'a'..'z' .
    digit = "0123456789" .
//    messageChar = '\u0020'..'\u007e' - ' ' - '(' - ')'  .

TOKENS

    double = ['-'] digit { digit } [ '.' digit { digit } ] .
    ident = letter { letter | digit | '_' } .
//    message = letter { messageChar } CONTEXT (')') .

// MessageText<out string m> = message               (. m = t.val; .)
// .

HearExpr<out HeardMessage message> =
    (.
        TimeSpan time; 
        Angle direction = Angle.NaN; 
        string messageText = ""; 
    .)
    "(hear" 
    TimeSpan<out time>
        ( "self" | AngleInDegrees<out direction> )
//         MessageText<out messageText>
    {
        ANY (. messageText += t.val; .)
    }
    ')'
    (. 
        message = new HeardMessage(time, direction, new Message(messageText)); 
    .)
    .

ANY будет читать символ, пока не попадет ')' или пробел. Я поместил его в цикл, объединяющий каждое значение, но вы можете этого не делать. Вы можете хотеть иметь это в цикле, хотя, чтобы он не возвращал «over», когда он видит «здесь», но «здесь». Вы можете выполнить простую проверку длины для messageText или другие проверки достоверности, такие как добавление t.val в список и проверку количества. Ничего действительно. Вы также можете выполнить тест с RegEx, чтобы убедиться, что он соответствует любому шаблону, с которым вам нужно проверять.

РЕДАКТИРОВАТЬ (8 апреля 2011 г.): Пример использования Coco / R с целыми и действительными числами

COMPILER Calculator
CHARACTERS
    digit       = "0123456789".

TOKENS
    intNumber    = ['-'] digit { digit } .
    realNumber   = ['-'] { digit } "." digit { digit } 
                         [("e" | "E") ["+" | "-"] digit {digit}] .

PRODUCTIONS
    Calculator  = { Expression "=" } .
    Expression  = Term { "+" Term | "-" Term }.
    Term        = Factor { "*" Factor | "/" Factor }.
    Factor      = intNumber | realNumber .

END Calculator.

РЕДАКТИРОВАТЬ (9 апреля 2011 г.)

Factor<out double value>
    (. value = 0.0; .)
= 
    ( 
        intNumber 
        (. value = Convert.ToDouble(t.val); .)
        | 
        realNumber 
        (. value = Convert.ToDouble(t.val); .)
    ) 
    | "(" Expression<out value> ")"         
.

или

Factor<out double value>
    (. value = 0.0; .)
=
    ( intNumber | realNumber ) 
    (. value = Convert.ToDouble(t.val); .)
    | "(" Expression<out value> ")"
.
2 голосов
/ 21 июня 2010

Возможно, вы захотите взглянуть на генератор PEG с контекстно-зависимым токенизацией.

http://en.wikipedia.org/wiki/Parsing_expression_grammar

Я не могу придумать, как вы справитесь с этим, используя COCO / R или подобное, так как каждый токен должен быть однозначным.

Если бы сообщения были окружены кавычками или каким-либо другим способом устранения неоднозначности, то у вас не было бы проблем. Я действительно думаю, что PEG может быть вашим ответом, так как он также упорядочил выбор (первый матч).

Также взгляните на:

http://tinlizzie.org/ometa/

1 голос
/ 15 июня 2010

Несмотря на название, похоже, все это относится к сканеру, а не к парсеру.Я не использовал CoCo / R, поэтому я не могу комментировать его напрямую, но в типичном (например, lex / Flex) сканере правила рассматриваются по порядку, поэтому выбранное правило / шаблон является первым, которыйМатчи.Большинство сканеров, которые я написал, включают «.»(то есть совпадение что-нибудь ) как их последний шаблон, чтобы отобразить сообщение об ошибке, если есть какой-либо ввод, который не соответствует ни одному другому правилу.

...