8

Вопрос по parsing, compiler-construction, language-agnostic – что подразумевается под самым левым выводом?

Пожалуйста, помогите мне понять, что подразумевается подLeft Most Derivation второйL в .LL Parser Объясните это на простейшем примере. Я видел следующую картину, объясняющуюСамый левый выводно я этого не понимаю

<span>Я думаю, что слева от деривации означает, что вы всегда применяете правило # к крайнему левому месту, где вы можете применить его. Так что я могу просто сказать:Правило N -&gt; N D &#39; и вы знаете, чтобы применить его в крайнем левом месте, которое вы можете. Если это был RR Parser, то это &#39;Примените это в самом правом месте, где это возможно.</span>

от Patashu

1 ответ

10

Правила грамматики отображаются слева с нетерминальными символами и терминальными символами. Нетерминальные символы должны быть заглавными буквами, все остальное обычно является терминальным символом. В примере N и D не являются терминалами, а 0-9 являются терминалами. Самый левый вывод ВСЕГДА заставляет самый левый нетерминал проходить через правило грамматики. Попытка отформатировать пример ниже.

N
=> N D   --Replaces the first/left most/only (which is "N") with the N => N D rule
=> N D D --Replaces the first/left most nonterminal (which is "N") with the N => N D rule
=> D D D --Replaces the first nonterminal (which is "N") with the N => D rule
=> 1 D D --Replaces the first nonterminal ("D") with the D => 1 rule(our first terminal character!)
=> 1 2 D --Replaces the first nonterminal ("D") with the D => 2 rule
=> 1 2 3 --Replaces the first nonterminal ("D") with the D => 3 rule
-- Only terminal characters remain, derivation/reduction is complete.

Похожие вопросы