Почему существуют парсеры LR(0), а парсеры LL(0) отсутствуют?
Я читал оба в Википедии и заметил, что, хотя парсеры LR(0) существуют, парсера LL (0) не существует.
Из того, что я прочитал, я понимаю, что k в LL (k) / LR(k) означает, сколько символов парсер может увидеть за пределами текущего символа, над которым он в данный момент работает.
Итак, мой вопрос: почему не существует такого понятия, как LL (0) парсер, даже если LR(0) существует?
1 ответ
Разница связана с тем, что означает k в LR(k) по сравнению с LL(k).
В LL (k) синтаксический анализатор хранит информацию о разборе сверху вниз, слева направо, который отслеживает крайний левый вывод. Парсер работает, многократно просматривая текущий нетерминальный символ, затем проверяя следующие k токенов входного потока, чтобы определить, какую продукцию следует использовать. В результате, если у вас есть анализатор LL(0), он должен будет предсказать, какую продукцию использовать, основываясь исключительно на текущем нетерминале. Это возможно только в том случае, если с каждым нетерминалом связана только одна продукция, что означает, что грамматика либо создает ровно одну строку, либо не содержит строк вообще (входя в цикл). Поэтому, хотя математически он хорошо определен, разбор LL(0) на практике никогда не используется.
В LR(k) парсер работает снизу вверх. Он поддерживает стек символов вместе с текущим "состоянием", а затем непрерывно решает, следует ли выполнить сдвиг (выталкивание другого символа поверх стека) или уменьшение (выталкивание некоторого количества символов из стека и применение производственного процесса). задом наперед). Одно ключевое отличие между анализатором LL (k) и LR(k) заключается в том, как анализатор LR(k) решает, какое действие выполнить. В парсере LR(k) решение о том, что делать дальше, основывается как на следующих k токенах предвидения, так и на текущем состоянии парсера. В результате синтаксический анализатор LR(0) все еще может принимать несколько разумные решения о том, какое действие выполнять, даже если он не видит никаких жетонов предварительного просмотра, потому что текущее состояние анализатора может закодировать огромное количество информации о том, где в производстве парсер и то, что он может реально ожидать увидеть в качестве следующих токенов ввода (даже если парсер не может напрямую просматривать эти токены).
Короче говоря, LL(0) чрезвычайно слаб, потому что анализатор должен просто основывать свое решение на текущем нетерминале, что означает, что он не может выполнить одно из многих различных действий, основанных на том, какое производство может быть использовано. Парсер LR(0) является достаточно мощным, потому что парсер основывает свой выбор на своем внутреннем состоянии, которое обычно достаточно подробно, чтобы позволить парсеру принимать обоснованные решения о том, что делать дальше.
Есть еще одна причина, по которой LL(0) слабая, а LR(0) достаточно мощная. В парсере LL(0) парсер должен немедленно решить, какие произведения следует выполнить, что означает, что парсер должен полностью слепо угадывать произведения. В парсере LR(0) парсер может сдвигать несколько символов, прежде чем решить, что пора уменьшать. Следовательно, синтаксический анализатор без какого-либо предварительного просмотра может отложить принятие решения о том, какое сокращение использовать, до тех пор, пока он не увидит достаточно токенов ввода, чтобы получить представление о структуре строки. Это частный случай более общего факта, что любая грамматика LL (k) автоматически становится LR(k).
Надеюсь это поможет!