ВУЗ:
Составители:
12
Примеры грамматик и языков:
Если при описании грамматики указаны только правила вывода Р, то бу-
дем считать, что большие латинские буквы обозначают нетерминальные сим-
волы, S – цель грамматики, все остальные символы – терминальные.
1) Язык типа 0: L = {a
2
b
n
2
1−
| n ≥ 1}
P: S → aaCFD
F → AFB | AB
AB → bBA
Ab → bA
AD → D
Cb → bC
CB → C
bCD → λ
2) Язык типа 1: L = {цепочки из 0 и 1 с одинаковым числом 0 и 1}
P: S → ASB | AB
AB → BA
A → 0
B → 1
3) Язык типа 2: L = {(ac)
n
(cb)
n
| n > 0}
P: S → aQb | accb
Q → cSc
4) Язык типа 3: L = { ω | ω ∈ {a,b}
+
, где нет двух рядом стоящих a}
P: S → A⊥ | B⊥
A → a | Ba
B → b | Bb | Ab
2. Построение грамматик. Грамматики,
описывающие основные конструкции
языков программирования
Задача построения формальных грамматик состоит в том, что для множе-
ства конечных цепочек, заданного в виде описания на естественном языке, тре-
буется построить формальную грамматику, порождающую это множество це-
почек. Учитывая, что терминальный словарь грамматики должен включать все
символы, используемые для построения цепочек, входящих в заданное множе-
ство, результатом решения задачи должны явиться нетерминальный словарь и
схема грамматики.
Построение этих объектов представляется достаточно сложным, поскольку
оно должно выполняться неформально и требует мысленного охвата всевоз-
можных допустимых вариантов цепочек заданного множества и синтеза правил
их построения. Построение усложняется еще и тем, что оно, как и всякая другая
задача синтеза, имеет много решений.
Страницы
- « первая
- ‹ предыдущая
- …
- 8
- 9
- 10
- 11
- 12
- …
- следующая ›
- последняя »
