Формальные языки и их задания

2.4. Ливорекурсивни и расширенные продукции Правило вида A Av называется ливорекурсивним . Если в грамматике есть продукции A Av | u , где u , то first ( Av ) = first ( u ) и грамматика не является LA (1) — грамматики. Но с помощью этих правил выводятся слова из множества { u , uv , uvv , ...}, которая задается регулярным выражением uv * или u { v }. Вместо продукций A Av | u запишем A u { v }. Продукции с регулярными выражениями в правой части называются расширенными , как и грамматики с такими продукции. Нетрудно убедиться, что расширенные правила не обогащают множество языков, порожденных КВ-грамматики. Пример 10. Расширенная грамматика G 01 правилам E T {+ T } T F {* F } F ( E ) | a эквивалентна грамматике G 0. Фактически РБНФ иному записью расширенных продукций, а совокупности РБНФ — другой формой расширенных КС-грамматик. 3.1. Правила построения Пусть G = ( X , N , P , S ) — LA (1) — грамматики без-правил, возможно, расширена. Опишем построение программы синтаксического анализа слов языка L ( G ). Программа будет включать процедуры, именами которых соответствующие им нетерминалы грамматики. Процедура, соответствующая нетерминалу A , описывает анализ цепочек, выводных с A . Этими цепочками являются слова языка или их под словом. Алгоритм процедуры такой. Пусть A w 1 | ...| w k — все продукции из нетерминалом A слева, a 1 a 2 ... a n — цепочка, начало которого надо выводить из A . Сначала определяется, какой из множеств first ( w 1), ..., first ( w k ) принадлежит символ a 1. Пусть им будет first ( w 1), и в простейшем случае w 1 = Y 1 Y 2 ... . Y m , где Y i — терминал или нетерминал. Начало цепочки должно выводиться из Y 1. Если Y 1 — терминал, то проверяется равенство a 1 = Y 1. Если Y 1 — нетерминал, то с a 1 начинается часть слова, выводной с Y 1, и для анализа начале цепочки a 1 a 2 ... вызывается процедура Y 1. В обоих случаях, после проверки равенства или возвращения из вызова Y 1, при некотором j 2 начало непроанализировано среза a j a j +1 ... должен выводиться из Y 2 и т. д. . Первый символ непроанализировано части цепочки называть текущим . Итак, за правыми частями w i продукций строятся фрагменты процедуры A ; они выполняются, когда текущий символ цепочки содержится в соответствующем множестве first ( w i ). Сделаем уточнение программы и правил построения процедур.
Взять кредит в Киеве
Пусть w — слово, анализируется, ch — его текущий символ, функция getc задает добычи следующего символа слова, переменная finch обозначает специальный символ, возвращается функцией getc после окончания слова w . Пусть ok — булевых переменная, что является признаком принадлежности w L ( G ), а процедура error задает присваивания ok = false . Телом программы является begin ok = true ; ch = getc; S; {Вызов процедуры, соответствующей} {главном нетерминалу} writeln ((ch = finch) and ok) end . Пусть A является нетерминалом с продукцией A w 1 | ...| w k , а S 1, ..., S k обозначают множества first ( w 1), ..., first ( w k ), которые не пересекаются. При таких условиях телом процедуры A является составной оператор begin if ch in S1 then оператор-для-w 1 else . ... if ch in S k then оператор-для — w k else error end В частности, если S i содержит только один символ x , то вместо условия ch in S i можно записать ch = x . Правые части расширенных грамматик являются выражениями, состоящими из последовательностей символов алфавита X и метасимволов, каковы скобки (), {} и символы |. Рассмотрим правую часть v расширенного правила как последовательность выражений Y 1 ... Y k , в которой Y i является или символом с X N , или выражением вида ( u ), или { u }, не содержится внутри других скобок, где u — последовательность нетерминалов, терминалов и скобок. По правой частью v строится составной оператор с последовательностью операторов, соответствующих Y 1, ..., Y k . Пусть Y обозначает один из выражений Y 1, ..., Y k . Соответствующий оператор определяется видом Y по следующим правилам.

  • Если Y является первым терминалом Y 1, то оператором является
ch = getc.
  • Если Y является терминалом, но не первым в цепочке v , то оператор имеет вид
if ch = Y then ch = getc else error то есть надо проверить совпадение текущего символа с Y и перейти к следующему символу.
  • Если Y является нетерминалом, то оператором вызов процедуры
Y.
  • Если Y имеет вид ( u 1 | ...| u m ) и T i обозначает first ( u i ) при i = 1, ..., m , то надо определить, к какой из множеств T i принадлежит текущий символ, и выполнить оператор, соответствующий u i
if ch in T 1 then оператор-для-u 1 else ... if ch in T m then оператор-для-u m else error.
  • Если Y имеет вид, T = first ( u ), то за выполнение условия ch T надо выполнить оператор, соответствующий u
if ch in T then оператор-для-u .
  • Если Y имеет вид { u } T = first ( u ), то за выполнение условия ch T надо повторять выполнения оператора, соответствующего u
while ch in T do оператор-для-u . В частности, когда цепочка u начинается терминалом, то есть u = xu 1, где x X , то цикл имеет вид while ch = x do begin ch = getc; оператор-для-u 1 end . Операторы, соответствующие u , u 1, ..., u m , записываются по этим же правилам. 3.2. Построение анализатора арифметических выражений Расширенная LA (1) — грамматики G 01 с продукцией E T {+ T } T F {* F } F ( E ) | a порождает язык арифметических выражений. Согласно приведенным правилам запишем процедуры E, T, F procedure E; begin T; while ch = '+' do begin ch = getc; T end end ; procedure T; begin F; while ch = '*' do
Комментарии и пинги к записи запрещены.

Комментарии закрыты.