Синтаксис и семантика языка

Синтаксис языка - это набор правил, определяющий допустимые конструкции языка. Синтаксис определяет «форму языка» - задает набор цепочек символов, которые принадлежат языку. Чаще всего синтаксис языка можно задать в виде строгого набора правил, но полностью это утверждение справедливо только для чисто формальных языков.

Например, строка «3+2» является арифметическим выражением, «3 2 +» - не является.

Семантика языка - это раздел языка, определяющий значение предложений языка. Семантика определяет «содержание языка» - задает значение для всех допустимых цепочек языка.

Например, используя семантику алгебры мы можем сказать, что строка «3+2» есть сумма чисел 3 и 2, а также то, что «3+2 = 5» - это истинное выражение

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

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

Формально порождающая грамматика G - это четверка G (VT, VN, P, S), где

VT - множество терминальных символов (терминалов),

VN - множество нетерминальных символов (нетерминалов), не пересекающееся с VT,

P - множество правил (продукций) грамматики вида a ® b, где aÎV⁺, bÎV*,

S - целевой (начальный) символ грамматики, S Î VN.

Для записи правил вывода с одинаковыми левыми частями

a ® b₁  a ® b₂ ... a ® b_n

будем пользоваться сокращенной записью

a ® b₁ | b₂ |...| b_n.

Каждое b_i , i = 1, 2, ... ,n , будем называть альтернативой правила вывода из цепочки a.

Такую форму записи правил грамматики называют формой Бэкуса-Наура. Она предусматривает также, что все нетерминальные символы берутся в <> скобки.

Пример: <число>::= <цифра>|<цифра><число>

<цифра>::= 0|1|2|3|4|5|6|7|8|9

Грамматики G1 и G2 называются эквивалентными, если L(G1) = L(G2).

Например,  G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S)

P1: S ® 0A1 P2: S ® 0S1 | 01

0A ® 00A1

A ® e

эквивалентны, т.к. обе порождают язык L(G1) = L(G2) = {0ⁿ1ⁿ | n>0}. Грамматики G1 и G2 называются почти эквивалентными, если L(G1) = L(G2) È {e}. Другими словами, грамматики почти эквивалентны, если языки, ими порождаемые, отличаются не более, чем на e.

Например,  G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S)

P1: S ® 0A1 P2: S ® 0S1 | e

0A ® 00A1

A ® e

почти эквивалентны, т.к. L(G1)={0ⁿ1ⁿ | n>0}, а L(G2)={0ⁿ1ⁿ | n>=0}, т.е. L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1) не входит.

Контекстно-свободная грамматика G называется неоднозначной, если существует хотя бы одна цепочка a Î L(G), для которой может быть построено два или более различных деревьев вывода.

Это утверждение эквивалентно тому, что цепочка a имеет два или более разных левосторонних (или правосторонних) выводов. В противном случае грамматика называется однозначной.

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

Пример неоднозначной грамматики:

G = ({if, then, else, a, b}, {S}, P, S),

где P = {S ® if b then S else S | if b then S | a}.

В этой грамматике для цепочки if b then if b then a else a можно построить два различных дерева вывода. Однако это не означает, что язык L(G) обязательно неоднозначный. Определенная нами неоднозначность - это свойство грамматики, а не языка, т.е. для некоторых неоднозначных грамматик существуют эквивалентные им однозначные грамматики. Если грамматика используется для определения языка программирования, то она должна быть однозначной.

В приведенном выше примере разные деревья вывода предполагают соответствие else разным then. Если договориться, что else должно соответствовать ближайшему к нему then, и подправить грамматику G, то неоднозначность будет устранена:

S ® if b then S | if b then S’ else S | a

S’ ® if b then S’ else S’ | a

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

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться: