0
Левая рекурсия заставит синтаксический анализатор перейти в бесконечный цикл. Так почему же это не происходит с правильной рекурсией?Почему правильные рекурсивные парсеры не чередуются бесконечно?
A
ответ
1
В рекурсивном анализаторе спуска правило грамматики, например A -> B C | D, реализуется путем попытки проанализировать B в текущей позиции, а затем, если это удастся, попытка проанализировать C в том месте, где B закончилась. Если либо сбой, мы попытаемся проанализировать D в текущей позиции¹.
Если C равно A (правая рекурсия), все в порядке. Это просто означает, что если B преуспевает, мы пытаемся проанализировать A в позиции после B, а это значит, что мы сначала пытаемся сначала проанализировать B, либо попробовать A снова в новой позиции, либо попробовать D. Это будет продолжаться до тех пор, пока, наконец, B не сработает и мы попробуем D.
Если B равно A (левая рекурсия), это очень проблематично. Поскольку теперь для разбора A мы сначала пытаемся проанализировать A в текущей позиции, которая пытается разобрать A в текущей позиции ... ad infinitum. Мы никогда не продвигаем свою позицию и никогда не пытаемся ничего, кроме A (которая просто продолжает пытаться сама), поэтому мы никогда не доберемся до точки, где мы могли бы прекратить свое существование.
¹ Предполагая полное отслеживание сзади. В противном случае A может потерпеть неудачу, не пытаясь D, если B и/или C потребляли какие-либо токены (или больше токенов, чем у нас есть, но это не имеет значения для этой дискуссии.
Можете ли вы представить свой код, чтобы мы могли помочь вы? Спасибо. –
@EdvinTenovim Мне не кажется, что есть какой-нибудь код для показа. Предположительно Шраддха в настоящее время работает с учебником по учебнику/курсом/учебником по компилятору/независимо от того, и, прочитав, что оставшаяся рекурсия в грамматике вызывает бесконечный циклы в рекурсивных парсерах спуска, задавался вопросом, почему это относится только к левой рекурсии. Это не смешной вопрос. – sepp2k
@EdvinTenovim Это теоретический вопрос о типах парсера. Это не имеет никакого отношения к фактическому коду. – EJP