Определение
Я считаю частичное совпадение ситуацией, в которой правило грамматики не совпадает, но может совпадать, если грамматика была изменена путем удаления конкатенаций. Рассмотрим следующую грамматику:
a ::= 'A' 'B' 'C' | 'A'
Первый вариант не соответствует вводу AB
, но может измениться, если грамматика была изменена путем удаления конкатенации 'C'
:
a ::= 'A' 'B' | 'A'
Я считаю это частичным соответствием .
Фон
Грамматика может иметь свойство, что все частичные совпадения являются индикаторами, что входные данные не будут совпадать. Рассмотрим следующую грамматику:
a ::= 'A' 'B' | 'B' 'C'
При реализации грамматики, подобной показанной выше, синтаксический анализатор может преждевременно прервать работу, если входные данные совпадают только частично. Для ввода A
синтаксический анализатор может прервать работу без проверки второй альтернативы, поскольку первая альтернатива была частичным совпадением.
О XML
В грамматике указаны W3C XML 1.0 Стандарт, похоже, обладает этим свойством в некоторой степени. Я обнаружил, что во многих местах частичное совпадение является фатальной ошибкой, то есть если сопоставление пробелов в начале правила не считается частичным совпадением. Рассмотрим следующий ввод:
<?xml version ?>
<foo></foo>
Он явно не правильно сформирован, потому что VersionInfo
частично совпадает в контексте, где это является фатальной ошибкой:
VersionInfo ::= S 'version' Eq ("'" VersionNum "'" | '"' VersionNum '"')
Дело в том, что действительно кажется, что язык был создан с учетом этого. Рассмотрим инструкции по обработке :
PI ::= '<?' PITarget (S (Char* - (Char* '?>' Char*)))? '?>'
PITarget ::= Name - (('X' | 'x') ('M' | 'm') ('L' | 'l'))
Это явно запрещает инструкции по обработке ориентироваться на xml! Без этого ограничения в PITarget
пример, показанный выше, на самом деле был бы хорошо сформирован!
Вопрос
Я всегда могу вручную найти места, где можно выручить досрочно, но это кажетсяболее общая концепция. Я надеюсь, что где-то в спецификации есть параграф, который гарантирует, что частичные совпадения (исключая пробелы) всегда являются фатальными ошибками. Это означало бы, что я мог бы просто написать вспомогательную функцию, чтобы сделать это автоматически, значительно упрощая реализацию.
У кого-нибудь есть встречный пример или какая-то гарантия?