Теория алгоритмов и формальных языков. Мелихов А.Н - 55 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

задания словесных ограничений, называемых контекстами, условиями языка,
которые включаются в его семантику.
Любая КС-грамматика G может порождать язык L(G), который может
быть пустым, конечным или бесконечным. Для того, чтобы язык L(G) был
непустым, необходимо и достаточно, чтобы в грамматике существовало по
крайней мере одно правило вывода вида
τ
→А , где А - нетерминал,
τ
-
терминальная цепочка. Правила такого вида называются терминальными. В
противном случае язык L(G) является пустым.
Для того, чтобы язык L(G), порождаемый грамматикой G, был
бесконечным, необходимо и достаточно, чтобы хотя бы для одного
нетерминального символа существовал вывод
ψ
yAА
G
→ , причем 0||||
≠
+
ψ
y .
В заключение отметим, что, строго говоря, все существующие языки
программирования порождаются не УКС-, а КС-грамматиками. УКС-
грамматики отличаются от КС-грамматик тем, что в них встречаются
укорачивающие правила. Такие правила имеют место тогда, когда
использование отдельных конструкция необязательно или зависит от задачи.
Очевидно, что проблема описания УКС-грамматик легко
решается, так как
для любой УКС-грамматики можно построить почти эквивалентную ей КС-
грамматику. Поэтому очень часто в качестве модели для описания
синтаксиса языков в программировании используют КС-грамматики. Только
что мы сказали о том, что УКС- и КС-грамматики можно использовать в
качестве модели языков программирования. Однако они все-таки
не
полностью отражают некоторые правила построения программ. Правила
языков программирования, которые не описываются средствами УКС- и КС-
грамматик, называют контекстными условиями. Большинство контекстных
условий (КУ) связаны с двумя особенностями языков программирования:
необходимостью представления объектов различных типов и наличием так
называемых областей действия. Первая особенность учитывается путем
описания типов переменных. Например,
в Алголе КУ этого типа описывают
все переменные как real, integer или Boolean. Знание типов объектов

Страницы