Отчет об ошибках в парсере рекурсивного спуска

Question

Я пишу рекурсивный анализатор спуска для конфигурационных файлов. Они в основном похожи на ini-файлы. Вот это язык, на каком-то EBNF-подобной форме:

document  ::= { category } 
category  ::= title {entry} 
title  ::= "[" <name> "]" 
entry  ::= <key> ":" <value> 

Вот пример файла, который должен дать ошибку синтаксического анализа в конце:

[Category1] 
key1:val1 
key2 :val2 
key3 : val3 

[Category2] 
key4: val4 

this line right here should produce an error 

Все примеры, которые я мог бы поиск в Интернете будет анализировать ввод до тех пор, пока не будет достигнут недопустимый символ, а затем прекратите работу без печати полезного сообщения об ошибке. У меня есть рабочий синтаксический анализатор, который следует этому поведению, но я не уверен, как реализовать полезную отчетность об ошибках.

Например, document состоит из 0 или более категорий. Что мне делать, когда первые две категории анализируются без ошибок, а третья содержит синтаксическую ошибку? Что делать, если вход заканчивается после второй категории, и я не могу разобрать третью категорию, потому что нет токенов слева (это не должно вызывать сообщение об ошибке)? Как я могу различать эти ситуации? Недействительная строка может быть сделана двумя способами: стать записью или стать заголовком. Это меня смущает.

Я хотел бы, чтобы моя программа печатала что-то вроде line 9: expected entry or title, когда она достигает последней строки вышеуказанного ввода. Как обычно люди выполняют сообщения об ошибках в парсерах рекурсивного спуска?

Answer 1

Я думаю, что вы спрашиваете, пару больших и не связанных между собой вопросов, я постараюсь на них ответить:

Что делать, когда первые две категории обрабатываются без ошибок, но третий содержит ошибка синтаксиса?

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

Что делать, если вход заканчивается после второй категории, и я не могу разобрать третью категорию, потому что нет лексем (это не должно вызывать сообщение об ошибке)? Как я могу различать эти ситуации?

Здесь нет проблем, поскольку вы говорите, так как соответствует стандарту document. Если вы запутались в реальной реализации, то это подробная информация о реализации (для которой вы не указали какой-либо код).

Может быть, вы должны попытаться визуализировать EBNF в более простой форме BNF, без расширения {}, вот один пример:

document  ::= category 
category  ::= title entries category | title entries 
title  ::= "[" <name> "]" 
entries  ::= entry | entries 
entry  ::= <key> ":" <value> 

Я лично считаю, представляя свою грамматику таким образом, приводит к более руководство для где вы нужна рекурсия. Например, в этом случае вам нужно попытаться разобрать category в синтаксическом оформлении символов category.Структура кода будет следовать, что более или менее - то есть, если он не может разобрать следующий символ в качестве категории, а затем возвращает истину в любом случае (с 2-го определения title entries следует)

Как люди обычно реализовать сообщения об ошибках в парсерах рекурсивного спуска?

У меня тот же вопрос сам, но, видя, что я не мог найти ответы на SO, я буду реализации его следующим образом:

1. Как я анализирую и есть маркеры, я хранить потребляемую длину.
2. Когда ошибка достигнута, не сразу бросайте ее - храните ее вместе с количеством токенов, которые были проанализированы.
3. В конце синтаксического анализа, в том числе возвратов, если нет распознаваемо решения, бросить ошибку, потребляемого большинство символов

Ключом является # 2. При внедрении анализатора рекурсивного спуска с обратным трассированием может быть выбрано несколько ложных срабатываний. Я думаю, что с точки зрения удобства использования, это, как правило, достойная эвристика, чтобы просто выбросить тот, который разбирался дальше всего.