Синтаксический анализатор проверяет порядок следование лексем для любого языка программирования. В основе синтаксического анализатора лежит аппарат формальных языков и грамматик.
Формальной грамматики Г называется совокупность четырех объектов.
Va – нетерминальные символы.
R – правила грамматики. Вида: a ->b, где a принадлежим Va. В принадлежит Vt,Va.
I принадлежит Va – Большие латинские буквы, символы, используемые для обозначения совокупности неких терминальных символов (например, последовательность лексем, образующий список переменных).
Vt – терминальные символы (символы допускаемые языком. Для упрощения ключевые слова, будем считать одним терминальным символом.
В теории компиляторов используется контекстно-свободная грамматика, для которой a меняется только на 1 нетерминальный символ.
Вывод – это замена, одного нетерминального символа на правую часть правила, ему соответствующему.
Например:
Множество конечных цепочек выводимых изначального символа грамматики называется языком порождаемый данной грамматикой. И обозначается L(Г).
Знак доллара означает пусто($):R->$.
Если в процессе вывода не содержится ни одной цепочки из терминальных символов, то такой язык называется пустым.
Например:
I-> iR | jR --- это правило можно заменить на: I-> iR, I->jR
R ->; iR | ;jR | $
I->iR->I;iR->I,I,jR
Синтаксический разбор
1) I->TS;
2) T-> int | char | float
3) S-> ABCR
4) A->*|$
5) B->i|j
6) C->[]|$
7) R->,S|$
Каким образом будет выводится вывод такой строчки: int *i,j,i[];
I->TS; -> intS; -> int ABCR; ->int *BCR; -> int *iCR; -> int *iR; -> int *i,S; ->int *i,ABCR; ->
int *i, BCR; -> int *i,jCR; -> int *i,jR; -> int *i,j,ABCR; -> int *i,j,BCR; -> int *i,j,CR; ->
int *i,j,i[];.
[1, 2.1, 3, 4.1, 5.1, 6.2, 7.1…]
Правило грамматики порождают цепочки или задают порядок их составления. При выводе обычно используется левосторонний вывод, при котором крайний левый нетерминальный символ меняется на правую часть правила, ему соответствующему. Правосторонний вывод даст аналогичный результат.
Перечень правил используемых при выводе, называются синтаксическим разбором. В языках программирования необходимо, чтобы для каждой цепочки был только один вывод.
Составление правил грамматики
Если все правила имеют закономерность, то это учитывается в правилах.
Пример 1:
main() { ………. }
main() { ………. }
То,
I -> mailA
Пример 2:
Если:
a = 10;
B = 10+ c;
D = e + k – 20;
То:
I -> A;
И так далее…
Повторение символов, называется списком. Пример: ааааааа….а.
Тогда:
I -> aR
R -> aR | $
Пример: a,a,a,a,a,a
I -> aR
R -> ,aR |$
Для построения правил грамматики необходимо:
- Выписать примеры цепочек. Проанализировать структуру цепочек, выделяя одни и те же символы в начале и в конце.
- Ввести обозначение в виде нетерминальных символов для сложных структур, состоящих из групп символов.
- Описать эти сложные структуры с помощью правил грамматики.
- Объединить все правила грамматики.
- Проверить с помощью вывода правильность получения цепочек.
Пример 1: построить правил грамматики для задания целых десятичных чисел.
123
2075
625310
Все цепочки начинаются от 1 до 9. И обозначим буквой А. Оставшийся список буквой R,
Правило:
1) I -> AR
2) A -> 1|2|3 .. |9
3) R -> AR | 0R | $
Проверим число 105:
I -> AR -> 1R -> 10R -> 10AR -> 105R -> 105
Пример 2:
Построить правило грамматики для задания десятичных вещественных чисел:
1) I -> AR.BR
2) A -> 1|2|3| .. |9
3) B ->0|A
4) R ->AR | BR | $
Пример 3: Составить правило грамматики для целых десятичных, восьмеричных и шестнадцатеричных чисел. Числа могут быть – и +.
105 - десятичное
0105 - восьмеричное
0х105 - шестнадцатеричное
-427 - десятичное
-055 - восьмеричное
-0хaf6 – шестнадцатеричное
Правило:
I -> AR | 0BR |0xCR
A -> 1|2|3| .. |9
B -> 1| 2| .. |7
C -> 1|2|3|..|9|A|B|C|D|E|F
R -> AR |BR| CR| $
Пример 4: Составить правило грамматики для описания целого и вещественного типа.
var a,b,a,b,a: integer;
var b,f:real;
Правило:
I -> var S:T;
S -> AR
R -> ,AR| $
A -> a| b
T -> integer | char
