к библиотеке   Устройства ввода информации   к экономической информатике   к дискретной математике

Теория формальных грамматик

  1. Порождающие грамматики
  2. Классификация формальных грамматик
  3. Порождение (вывод)
  4. Перевод (трансляция)
  5. Схема синтаксически управляемого перевода
  6. Транслирующие грамматики
  7. Атрибутные грамматики и трансляция
  8. Синтаксический анализ
  9. Нисходящий синтаксический анализ
  10. Нерекурсивный предиктивный анализ
  11. Множества FIRST и FOLLOW
  12. Восходящий синтаксический анализ
  13. Литература
Для понимания информационных процессов, происходящих при трансляции необходимо иметь представление о иерархических уровнях информации:

  1. комбинаторная, морфологическая информация - информация, представляемая мерой разнообразия вариантов, пространство выбора. Примерами служат единицы комбинаторной информации: буква, знак, двоичный разряд, байт, килобайт, мегабайт...
  2. статистическая информация, энтропия Больцмана (Шеннона), негэнтропия Бриллюэна - информация представляемая статистическими мерами, возникающими при повторении измерения, принятия решений на выборках. Примеры единиц такой информации: бит, нит, килобит...
  3. лексическая информация - информация, представляемая структурами своих носителей - лексем, являющихся альтернативами при принятии решений, классификации, распознавании альтернатив. Примерами служат слова, термины, операторы языка.
  4. синтаксическая информация - информация, отражающая структуру сообщений: предложений, операторов и пр. Примерами служат предложения естественного языка, законченные конструкции из операторов компьютерных языков, логические утверждения.
  5. семантическая информация - информация, отражающая смысл сигналов, данных, сообщений. Примерами служат модели, создаваемые при анализе информации человеком и транслятором.
  6. прагматическая информация - информация, отражающая меру целевой ценности сообщений, тактическую, текущую полезность как соотнесение внешней по отношению к информации физической меры ценности к объему данных или сигналов, обеспечивающих эту физическую меру. Примерами служат денежная стоимость информационной справки, цена обучения и т.п.
  7. системная информация - информация, отражающая меру системно-критериальной ценности сообщений, стратегическую полезность, выражающуюся как отношение меры существования целевой системы к объему необходимых для этого существования данных.

Порождающие грамматики

Определение. Терминалы, нетерминалы, символы. Продукции. Стартовый символ.

Обозначения:

a,b,c, ... - терминалы
u,v,w,x,y,z - строки (цепочки) терминалов
A,B,C, ... - нетерминалы
α,β,γ, ... - строки (цепочки) нетерминалов и терминалов
ε - пустая цепочка

Опр. формальной грамматики (порождающей грамматики Хомского)

G = (N,Σ,P,S)
N - нетерминалы
Σ - терминалы
P - правила вывода (продукции) вида α→β, α - непустая 

V = Σ + N - множество всех нетерминалов и терминалов

V* - множество всех цепочек символов из V

V+ = V* - {ε}

Классификация формальных грамматик по Хомскому

Правила имеют вид αAβ → αγβ. γ принадлежит V+, т.е. грамматика является неукорачивающей
α,β называются левым и правым контекстом
Правила имеют вид A → α. α принадлежит V*, т.е. грамматика может быть укорачивающей => КС языки не содержатся в КЗ
Наиболее близкая к БНФ
Правила имеют вид A → aB, A → a, A → ε
Автоматные языки содержатся в КС языках

Пример. Грамматика, порождающая язык правильных скобочных выражений.

S → (S) | SS | ε

Порождение (вывод)

Обозначения

=>
=>+ (1 или более)
=>* (0 или более)
Сентенциальная форма грамматики - это строка, которая может быть выведена из стартового символа.
Предложение (сентенция) грамматики - это сентенциальная форма, состоящая из одних терминалов.
Язык L(G) грамматики - это множество всех ее предложений.

Обозначения:

=>(lm)
=>(lm)*
=>(rm)+

Левый, правый вывод (порождение).

Пример

E → E + T
  | T
T → T * P
  | P
P → i
  | ( E )

Левый и правый вывод для предложения i + i * i

Дерево вывода (синтаксическое дерево, дерево разбора) строки предложения. В отличие от порождения, из него исключена информация о порядке вывода.

Крона дерева разбора - цепочка меток листьев слева направо

Грамматика, которая дает более одного дерева разбора для некоторого предложения, называется неоднозначной.

Пример неоднозначной грамматики. Грамматика арифметических выражений.

E → E+E | E*E | i

Два дерева разбора для цепочки i + i * i

Преобразование в эквивалентную однозначную грамматику:

E → E + T
  | T
T → T * P
  | P
P → i

Пример неоднозначной грамматики. Грамматика условного оператора

S → if b then S
  | if b then S else S
  | a  

Два дерева разбора для цепочки if b then if b then a

Преобразование в эквивалентную однозначную грамматику:

S → if b then S
  | if b then S2 else S
  | a  
S2 → if b then S2 else S2
  | a  

Утверждение. Проблема неоднозначности произвольной КС-грамматики алгоритмически не разрешима

Леворекурсивные грамматики, их проблемы. Алгоритм устранения левой рекурсии.

Перевод (трансляция)

Ранее мы решали вопрос о принадлежности некоторой цепочки α интересующему нас языку L, задаваемому грамматикой G. Но задача компиляции шире: не только распознать входную цепочку, но и сгенерировать выходную.

Определение.

Перевод с языка L1 на язык L2 - Пусть Σ и Δ - два алфавита (называемые "входным" и "выходным" соответственно). L1 ⊂ Σ*, L2 ⊂ Δ*. Переводом с языка L1 на язык L2 называется отображение τ: L1 → L2.

Чтобы решить указанную задачу (т.е. конструктивно определить перевод), можно встроить в процесс проверки принадлежности некоторые действия, формирующие на выходе желаемый результат.

Схема синтаксически управляемого перевода (СУ-схема)

СУ-схема - это грамматика, в которую с каждым синтаксическим правилом встроен элемент перевода.

Пример. Перевод алгебраического выражения в ПОЛИЗ (польская инверсная запись). Запишем правила грамматика вместе с элементами перевода.

Правило Элемент перевода
E → E + T E = E T +
E → T E = T
T → T * P T = T P *
T → P T = P
P → (E) P = E
P → <id> P = <id>

Выведем цепочку a * (b + c) и одновременно переведём её в ПОЛИЗ: a b c + * (как обычно, используем левый вывод):

(E, E) ⇒ (T, T) ⇒ (T * P, T P *) ⇒ (P * P, P P *) ⇒ (a * P, a P *) ⇒ (a * (E), a E *) ⇒
       ⇒ (a * (E + T), a E T + *) ⇒* (a * (b + c), a b c + *)

Определение.

Схема синтаксически управляемого перевода - это пятёрка

T = (N, Σ, Δ, R, S),

где:

N - множество нетерминалов ("переменных"),
Σ - входной алфавит,
Δ - выходной алфавит,
S - стартовый символ (S ∊ N),
R = {A → (α, β) | A ∊ N, α ∊ (N ∪ Σ)*, β ∊ (N ∪ Δ)*}.

Причём α и β в каждом конкретном правиле содержат одни и те же нетерминалы с точностью до перестановки.

Далее считаем, что задана некоторая СУ-схема T = (N, Σ, Δ, R, S).

Определение.

Входная грамматика, соответствующая СУ-схеме T - это четвёрка

Gin = (N, Σ, R, S),

где

P = {A → α | ∃β A → (α, β) ∊ R}.

Определение.

Выходная грамматика, соответствующая СУ-схеме T - это четвёрка

Go = (N, Δ, R, S),

где

P = {A → β | ∃α A → (α, β) ∊ R}.

Определение.

СУ-перевод, СУ-трансляция - это множество

{(x, y) | (S, S) ⇒* (x, y), x ∊ Σ*, y ∊ Δ*},

обозначаемое обычно τ(T).

СУ-перевод можно понимать как трансформацию синтаксических деревьев (соответствующих выводу входной и выходной цепочек).

Транслирующие грамматики

Позволяют решать задачу перевода в более сложных случаях, чем СУ-схемы. ТГ это разновидность КС-грамматик, где символы (терминалы) разделены на два множества, Σi и Σa (a от action), называемые "входными" и "операционными" соответственно. При использовании ТГ, чтобы различать элементы Σi и Σa, будем заключать последние в фигурные скобки, '{', '}', считая получившиеся на письме три символа одним символом алфавита.

Пример. Перевод простого алгебраического выражения в ПОЛИЗ ...

Определение.

активная цепочка - Пусть α ∊ (Σi ∪ Σa)*. Тогда α называется активной цепочкой. Входные (операционные) символы активной цепочки, записанные отдельно в том же порядке, как они встречались в ней, образуют входную (операционную) цепочку.

Операционные символы можно трактовать как имена процедур, выполняющих определённые действия. Пока - процедур без параметров. Операционные символы также могут использоваться для интерпретации кода. Операционные символы могут находиться в любой части результата продукции, не только в суффиксе, но это может сильно усложнить парсер (иногда придётся откатываться).

Атрибутные грамматики и трансляция

В АГ с каждым символом грамматики может быть связан один или несколько атрибутов. Для каждого синтаксического правила вводятся семантические правила, устанавливающие функциональные зависимости между атрибутами.

Дерево, содержащее атрибуты, называется аннотированным. Атрибуты придают смысл синтаксической структуре, описываемой деревом, и потому аннотированное дерево называется также семантическим деревом.

Пример. Вычисление простого арифметического выражения ...

Типы атрибутов.

  1. Синтезированные - значения таких атрибутов зависят только от значений атрибутов потомков в дереве разбора.
  2. Унаследованные - значения таких атрибутов зависят от значений атрибутов родительского узла, узлов-братьев и сестёр (дочерних для родительского), а также других атрибутов самого узла.

Синтаксический анализ

Понятие синтаксического анализатора.

Нисходящие (top-down) и восходящие (bottom-up) синтаксические анализаторы

Нисходящий синтаксический анализ

Предиктивный синтаксический анализатор - это синтаксический анализатор, работающий методом рекурсивного спуска и не требующий откатов.

Нерекурсивный предиктивный анализ

Схема работы со стеком, таблицей разбора, входным буфером

Алгоритм нерекурсивного предиктивного анализа

Пример

Множества FIRST и FOLLOW

Определение.

Пример.

Алгоритм построения таблиц предиктивного анализа.

Определение LL(1) грамматики. Пояснение названия.

Утв. LL(1) грамматика не может быть леворекурсивной или неоднозначной.

Эквивалентное определение LL(1) грамматики.

Восстановление после ошибок в предиктивном анализе.

Восходящий синтаксический анализ

Наиболее распространенная разновидность - ПС-анализ (перенос-свертка - shift-reduce)

Понятие основы. Примеры.

Обращенное правое порождение и обрезка основ.

Стековая реализация ПС-анализа. Основные операции:

Перенос (shift)
Свертка (reduce)
Допуск  (accept)
Ошибка  (error)

Утв. Основа всегда находится на вершине стека и никогда - внутри него. Доказательство.

Понятие активного префикса.

LR-анализаторы. SLR, канонический LR и LALR анализаторы.

Общая схема и алгоритм LR-анализа. Пример.

LR-грамматики.

Неоднозначности вида shift-reduce и их разрешение.

Литература

  1. Ахо А., Сети Р., Ульман Д. Компиляторы. Принципы, технологии, инструменты. - М.: Вильямс, 2001.
  2. Карпов Ю. Г. Основы построения трансляторов. - М.: BHV, 2005.
  3. Свердлов С. З. Языки программирования и методы трансляции. - М.: Питер, 2007.
  4. Опалева Э. А., Самойленко В.П. Языки программирования и методы трансляции. - М.: BHV, 2005.
  5. Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. - 2-е изд. - М.: Вильямс, 2008. - ISBN 978-5-8459-1349-4
  6. Робин Хантер Основные концепции компиляторов = The Essence of Compilers. - М.: "Вильямс", 2002. - С. 256. - ISBN 5-8459-0360-2
к библиотеке   Устройства ввода информации   к экономической информатике   к дискретной математике
Знаете ли Вы, что любой разумный человек скажет, что не может быть улыбки без кота и дыма без огня, что-то там, в космосе, должно быть, теплое, излучающее ЭМ-волны, соответствующее температуре 2.7ºК. Действительно, наблюдаемое космическое микроволновое излучение (CMB) есть тепловое излучение частиц эфира, имеющих температуру 2.7ºK. Еще в начале ХХ века великие химики и физики Д. И. Менделеев и Вальтер Нернст предсказали, что такое излучение (температура) должно обнаруживаться в космосе. В 1933 году проф. Эрих Регенер из Штуттгарта с помощью стратосферных зондов измерил эту температуру. Его измерения дали 2.8ºK - практически точное современное значение. Подробнее читайте в FAQ по эфирной физике.

НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
 26.04.2017 - 22:30: СОВЕСТЬ - Conscience -> ПРОБЛЕМА КРИМИНАЛИЗАЦИИ ЭКОНОМИКИ - Карим_Хайдаров.
26.04.2017 - 21:28: СОВЕСТЬ - Conscience -> Просвещение от Михаила Делягина - Карим_Хайдаров.
26.04.2017 - 19:10: СОВЕСТЬ - Conscience -> Просвещение от Константина Сёмина - Карим_Хайдаров.
26.04.2017 - 16:44: СОВЕСТЬ - Conscience -> РУССКИЙ МИР - Карим_Хайдаров.
25.04.2017 - 19:16: Беседка - Chatter -> ФУТУРОЛОГИЯ - прогнозы на будущее - Карим_Хайдаров.
25.04.2017 - 03:11: СОВЕСТЬ - Conscience -> КОЛЛАПС МИРОВОЙ ФИНАНСОВОЙ СИСТЕМЫ - Карим_Хайдаров.
25.04.2017 - 00:47: АСТРОФИЗИКА - Astrophysics -> Происхождение тектитов и кимберлитов. Кометные молнии. - Евгений_Дмитриев.
25.04.2017 - 00:32: СОВЕСТЬ - Conscience -> Проблема государственного терроризма - Карим_Хайдаров.
25.04.2017 - 00:29: СОВЕСТЬ - Conscience -> Просвещение от Ю.Ю. Болдырева - Карим_Хайдаров.
23.04.2017 - 05:25: СОВЕСТЬ - Conscience -> Просвещение от Марата Мусина - Карим_Хайдаров.
22.04.2017 - 05:49: СОВЕСТЬ - Conscience -> Проблема народного образования - Карим_Хайдаров.
20.04.2017 - 19:38: СОВЕСТЬ - Conscience -> Декларация Академической Свободы - Карим_Хайдаров.
Bourabai Research Institution home page

Bourabai Research - Технологии XXI века Bourabai Research Institution