Я не понимаю это предложение из статьи в Википедии, посвященной проблеме оборванного остального :
[Проблема Dangling Else] - это проблема, которая часто возникает при построении компилятора, особенно при анализе без сканирования.
Может кто-нибудь объяснить мне, как методы анализа без сканирования могут обострить эту проблему? Мне кажется, что проблема в грамматике, поскольку она неоднозначна, а не в выборе метода синтаксического анализа. Что мне не хватает?
if a then if b then s1 else s2
, то грамматика неоднозначна.Ответы:
Мое лучшее предположение состоит в том, что предложение в статье в Википедии является результатом неправильного понимания работы Э. Виссера.
Грамматики для синтаксических анализаторов (т. Е. Грамматики, описывающие язык как набор последовательностей символов, а не как набор последовательностей токенов с токенами, описанными отдельно как строки символов), как правило, имеют много неясностей. E. Visser paper Фильтры устранения неоднозначности для бессканерных обобщенных анализаторов LR (*) предлагает несколько механизмов для устранения неоднозначностей, один из которых полезен для решения висящей проблемы. Но в статье не утверждается, что точная неоднозначность, называемая «висячей проблемой», связана с синтаксическими анализаторами без сканера (и даже с тем, что механизм особенно полезен для анализаторов без сканера).
Тот факт, что он предлагает механизм для его решения, не является неявным утверждением, поскольку другой механизм разрешения неоднозначности (приоритет и приоритет оператора) также кажется совершенно не связанным с природой рассматриваемых синтаксических анализаторов без сканера (рассмотрим, например, что эти неоднозначности не могут быть присутствует в регулярных грамматиках, поскольку они являются результатом вложенности, в то время как те, которые обрабатываются правилом самого длинного соответствия, могут).
(*) Это, вероятно, статья, послужившая основой статьи в Википедии о парсерах без сканера, даже если они ссылаются на другой, в том числе Э. Виссер, Scannerless Scanner Generalized-LR .
источник
Просто для того, чтобы заявить о проблеме, проблема «оборванного остального» - это двусмысленность в спецификации синтаксиса кода, где она может быть неясной, в случае использования следующих if и elses, что еще принадлежит к которому if.
Самый простой и классический пример:
Это неясно для тех, кто не знает специфику языковой спецификации наизусть, которая
if
получаетelse
(и этот конкретный фрагмент кода действителен на полдюжине языков, но может работать по-разному в каждом).Конструкция Dangling Else создает потенциальную проблему для реализаций синтаксического анализатора без сканера, потому что стратегия состоит в том, чтобы отбрасывать файловый поток по одному символу за раз, пока синтаксический анализатор не обнаружит, что ему достаточно токенизации (дайджест в ассемблер или промежуточный язык, который он компилирует) , Это позволяет парсеру поддерживать минимальное состояние; как только он решит, что у него достаточно информации для записи токенов, которые он анализирует в файл, он сделает это. Это конечная цель синтаксического анализатора без сканера; быстрая, простая, легкая сборка.
Предполагая, что символы новой строки и пробелы до или после знаков препинания не имеют смысла (как они есть в большинстве языков стиля C), это утверждение будет выглядеть для компилятора как:
Отлично разбирается в компьютере, так что посмотрим. Я получаю по одному персонажу за раз, пока не получу:
О, я знаю, что это значит (в C #), это означает «
push
условиеA в стек eval, а затем вызов,brfalse
чтобы перейти к оператору после следующей точки с запятой, если это не так». Прямо сейчас я не вижу точку с запятой, поэтому сейчас я установлю свое смещение перехода на следующий пробел после этой инструкции и увеличу это смещение, вставляя дополнительные инструкции, пока не укажу точку с запятой. Продолжая разбирать ...Хорошо, это анализирует аналогичную пару операций IL и выполняется сразу после только что проанализированной инструкции. Я не вижу точку с запятой, поэтому я увеличу смещение перехода моего предыдущего оператора на длину двух моих команд (одну для толчка и одну для перерыва) и продолжу поиск.
Хорошо это легко Это "
call
DoFoo". И это точка с запятой, которую я вижу? Ну, это здорово, это конец строки. Я увеличу смещение прыжков обоих блоков на длину этих двух команд и забуду, что мне было все равно. ОК, двигаясь дальше ...... э-э-э Это не так просто, как казалось. Хорошо, я забыл, что я только что делал, но это
else
означает, что где-то есть условный оператор прерывания, который я уже видел, так что позвольте мне оглянуться назад ... да, вот оноbrfalse
, сразу после того, как я нажимаю "conditionB" на стек, что бы это ни было. Хорошо, теперь мне нужно безусловноеbreak
следующее утверждение. Заявление, которое придет после этого, теперь определенно является целью моего условного перерыва, поэтому я позабочусь о том, чтобы все было правильно, и увеличу безусловный разрыв, который я вставил.Это легко. "
call
DoBar". И есть точка с запятой, и я никогда не видел скобок. Итак, безусловноеbreak
должно перейти к следующему утверждению, что бы это ни было, и я могу забыть, что меня это когда-либо волновало.Итак, что у нас есть ... (примечание: сейчас 22:00, и мне не хочется преобразовывать битовые смещения в шестнадцатеричное или заполнять полную оболочку IL функции этими командами, так что это просто псевдо-IL используя номера строк, где обычно бывают смещения байтов):
Что ж, это на самом деле выполняется правильно, ЕСЛИ правило (как в большинстве языков стиля C) состоит в том, что оно
else
подходит ближе всегоif
. С отступом, чтобы следовать за вложением выполнения, он будет выполняться так, где, если условие A ложно, весь остаток фрагмента пропускается:... но это происходит благодаря счастливой случайности, потому что разрыв, связанный с внешним
if
оператором, переходит наbreak
оператор в конце внутреннего элементаif
, который переводит указатель выполнения за весь оператор. Это лишний ненужный переход, и если бы этот пример был более сложным, он мог бы больше не функционировать, если бы таким образом анализировал и разбивал токены.Кроме того, что если в спецификации языка сказано, что висячий элемент
else
принадлежит первомуif
, а если условие A ложно, то выполняется doBar, а если условие A истинно, но не условие B, то ничего не происходит, как это происходит?Синтаксический анализатор забыл о первом
if
существующем, и поэтому этот простой алгоритм синтаксического анализа не будет генерировать правильный код, не говоря уже об эффективном коде.Теперь синтаксический анализатор может быть достаточно умен, чтобы запомнить
if
s иelse
s, которые он имеет в течение более длительного времени, но если спецификация языка говорит, что одинарноеelse
после двухif
s соответствует первомуif
, это вызывает проблему с двумяif
s с совпадающимиelse
s:Парсер увидит первый
else
, соответствует первомуif
, затем увидит второй и впадет в панику в режиме «что, черт возьми, я делал снова». На этом этапе синтаксический анализатор получил довольно много кода в изменчивом состоянии, которое он, скорее всего, уже вытолкнул бы в выходной файловый поток.Есть решения для всех этих проблем и что-если. Но либо код, который должен быть настолько интеллектуальным, увеличивает сложность алгоритма синтаксического анализатора, либо спецификация языка, позволяющая парсеру быть таким тупым, увеличивает многословность исходного кода языка, например, требуя завершающие операторы типа
end if
или скобки, указывающие на вложенность блокирует, если вif
операторе естьelse
(оба из них обычно видны в других языковых стилях).Это всего лишь один простой пример пары
if
утверждений, в которых рассматриваются все решения, которые должен был принять компилятор, и где он мог бы все равно легко испортиться. Это деталь этого безобидного утверждения из Википедии в вашем вопросе.источник