ЛКШ. Зима.09. С + В. М. Гуровиц,

Язык множество строк Синтаксис набор правил, определяющих принадлежность строки языку Семантика набор правил, определяющих значение строки Общие определения

Язык все строки из нулей и единиц Синтаксис каждая строка содержит хотя бы один символ, и все символы – нули или единицы. Семантика каждая строка трактуется как число в двоичной системе счисления. Примеры

Язык – арифметические выражения Семантика : выражение 0/0 является синтаксически корректным, но семантически не имеет смысла. Примеры

Форма Бэкуса - Наура – формальная система описания синтаксиса. ::= '+' | '-' ::= 'for' ':=' ('to' | 'downto') 'do' БНФ

Пример : E+35 ::= [ ] { } [ { }] [ [ ] { }] ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ::= '+' | '-' ::= '.' ::= 'E' | 'e' Вещественное число : БНФ

// ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' function IsDigit(Ch : Char) : Boolean; begin Result := ( Ch in ['0'.. '9'] ); end ; Код

// ::=[ ] { } … function IsNumber( const S : string ) : Boolean; var P : Integer; begin Result := False; if Length(S) = 0 then Exit; P := 1 ; if IsSign(S[P]) then Inc(P); if (P > Length(S)) or not IsDigit(S[P]) then Exit; repeat Inc(P) until (P > Length(S)) or not IsDigit(S[P]); … Код

Синтаксическая диаграмма

Числа и арифметические операции +,, *, / Операции выполняются слева направо без учета приоритета ::= { } ::= '+' | '-' | '*' | '/' Простое выражение

// Выделяет из строки S число начиная с позиции P function Number( const S : String ; var P : Integer ) : Extended; function IsOperation(Ch : Char ) : Boolean ; // Проверка строки на соответствие // и вычисление выражения function Expr( const S : String ) : Extended ; Код

function Number( const S : string ; var P : Integer):Extended; var InitPos : Integer; begin InitPos := P; if (P Length(S)) or not IsDigit(S[P]) then halt(1) … Result := StrToFloat( Copy (S, InitPos, P InitPos) ); end; Function Number(…)

function Expr( const S : string ) : Extended; begin P := 1 ; Result := Number(S,P); while (P

2 + 2 * 2 = 8 А теперь переходим к самому интересному … Но …

2 + 3*4/5 6/7/8 9 ::= { } ::= '+' | '-' ::= '*' | '/' Порядок действий

function Term( const S: string ; var P:Integer):Extended; … Result:=Number(S,P); while (P

function Expr ( const S: string ) : Extended; … P:= 1 ; Result:=Term(S,P); while (P

::= { } ::= | '(' ')' Выражения со скобками

2+(3-4*2)+1222(3-4*2) 3-4*23334* Пример ::= { } ::= | '(' ')'

Рекурсивное определение ::= { } ::= | '(' ')' Рекурсивный код

// функция Expr должна быть объявлена до использования function Expr( const S : string ; var P : Integer) : Extended; forward ; function Term … begin …Expr(…); end ; … function Factor( const S : string ; var P : Integer):Extended; begin … end ; …; forward;

… напишите самостоятельно Код

(1 2) +(1 2) ((3)) ::= { } ::= | | '(' ')' ::= ______ { } [ { }] [ [ ] { }] ::= '+' | '-' Что мы забыли

Sin(pi/3*x)+4^(2x)^y-cos x/x^2 1) Лексический анализ – разбиение на лексемы и проверка их корректности Sin ( pi / 3 * x ) + 4 ^ ( 2x ) ^ y - cos x / x ^ 2 2) Синтаксический анализ – порядок действий, проверка синтаксиса выражения. 3) Семантический анализ – выполнение операций и проверка семантической корректности выражения ( деление на 0 и т. п.) Более сложные случаи

(A + B)(C + D) – E Дерево синтаксического разбора -* + AB+DCE

(A + B)(C + D) – E Обратная польская запись -* + AB+DCE A B + C D + * E -