Sémantika programovacích jazyk : Syntaxe a sémantika
Syntaxe a sémantika Programovací jazyky, syntaxe, sémantika, zp soby popisu T i hlavní charakteristiky jazyka (sémiotika) jsou: - syntax, sémantika a pragmatika jazyka Zhruba: syntaxe se zabývá formou (znaky a jejich vztahy), sémantika významem znak , pragmatika závislostí konstrukcí na nositeli Sémantika – odr da sémiotiky, kde se jako znaky používají symboly abecedy písmena, sémiotika je obecn jší nauka o znakových systémech. Oblastí jejího zájmu nejsou jen jazykové znaky, ale obecn i všechny ostatní znakové systémy (piktogramy, dopravní zna ky apod.). Nap . dopravní zna ka je symbol, její tvar ur uje kategorii, obrázek význam. Vlastní znakové systémy s pravidly gramatickými i sémantickými mají mj. um lecké obory, náboženství, hry nebo rituály. Za zakladatele moderní sémiotiky je považován americký filosof Charles Peirce (1839–1914), jenž rozd lil znaky na ikony, indexy a symboly. Sémantika je nauka o významu jednotlivých slov, morfém a jiných znak , p ípadn též jejich vztahu ke skute nosti, kterou ozna ují. Slovo vzniklo z eckého , séma znamená význam (nap . semafor = nosi významu). Vazbami mezi jednotlivými znaky t mito slovy se zabývá syntax. Sémantika je sou ástí sémiotiky, která se zabývá celými znakovými systémy. formáln : A ≠ ∅ neprázdná kone ná množina - abeceda jazyka. Syntaxe se zabývá vymezením formálního jazyka L ⊆ A* jako podmnožiny et zc nad abecedou, které tvo í správné zápisy v daném jazyce - v ty jazyka. P ívlastek formální vyjad uje nep ítomnost definice významu zápis . Sémantika pak definuje pro každou syntakticky správnou v tu jazyka (syntakticky správný program p ∈ L) jeho význam. Pragmatika se u programovacího jazyka neuvažuje.
Sémantika (p es jazykovou rovnost): Sémantika úzce souvisí s jazykovou rovností ≅ ⊆ L × L Libovolnou binární relaci ≅ ⊆ L × L, která má vlastnosti ekvivalence (je reflexivní, symetrická a tranzitivní), lze nazvat jazykovou rovností a považovat za definici sémantiky jazyka. Jazykovou rovností je ur eno, které zápisy jsou významov ekvivalentní - mají stejný význam. Jazyková rovnost indukuje na množin L rozklad, jehož t ídy p edstavují možné významy v abstraktním smyslu (až na izomorfismus). P .: Jazyk binárních zápis p irozených ísel Syntax: A = { 0, 1 }, L = A* - { e } (neprázdné et zce nad A) Karel Richta
1
Sémantika programovacích jazyk : Syntaxe a sémantika Sémantika (p es jazykovou rovnost): jazyková rovnost pro jazyk binárních zápis je nejmenší ekvivalence na L generovaná axiomem: ∀ x ∈ L. ( x ≅ x ) ∧ ( x ≅ x )
( 0x ≅ x ), tj.
≅ = { <x,x> | x ∈ L } ∪ { <0x,x> | x ∈ L } Množina všech syntakticky správných binárních zápis p irozených ísel L se rozpadne na faktorovou množinu L/≅ [ 0 ] = { 0, 00, 000, ... } [ 1 ] = { 1, 01, 001, ... } [ 10 ] = { 10, 010, 0010, ... } , ... L/≅ je izomorfní (jako množina) s množinou p irozených ísel Nat. Odpovídajícím morfismem je libovolné kódování (bijektivní zobrazení) k: L/≅ → Nat, kterým lze stanovit, jaké p irozené íslo k(x) zastupuje t ída ekvivalence [ x ] ∈ L/≅ a tedy i které p irozené íslo ozna uje zápis x (a rovn ž všechny zápisy ekvivalentní s x, tj. všechna y taková, že y ≅ x).
Sémantika (pomocí modelu): Postupovat lze i obrácen - nejprve definovat zamýšlený model M význam jazykových konstrukcí. M p edstavuje universum význam - každý výraz jazyka ozna uje n který prvek M (obrácen to platit nemusí). Poté ur íme interpretaci výraz v M, tj. zobrazení int: L → M. Jazyková rovnost je pak ur ena nep ímo - dva výrazy jsou ekvivalentní práv tehdy, když mají stejnou interpretaci: x ≅ y ⇔ int[x]== int[y], kde == ⊆ M × M je identita na M.
Syntaxe programovacích jazyk Programovací jazyky mají nej ast ji kontextový charakter, který je dán zejména deklaracemi. P estože existují speciální kontextové gramatiky, jejich použití není rozší eno, nebo bezkontextové gramatiky jsou mnohem propracovan jší a pružn jší. Obvykle se proto pro popis syntaxe programovacích jazyk používají nejvýše bezkontextové gramatiky, což souvisí s tím, že pro každý kontextový jazyk existuje bezkontextový nadjazyk, který jej obsahuje (d kaz dále). Kontextové závislosti (omezení) se pak vyjad ují jinými prost edky. Náznak d kazu: dle klasifikace gramatik podle Chomského
Gramatika:
, S ∈ N Podle tvaru pravidel z P: (A,B ∈ N, a ∈ T, α ,γ ,δ ∈ (N ∪ T)* , β ∈ (N ∪ T)+ ) regulární: A → a nebo A → aB
(kone ný automat)
bezkontextová: A → α
(zásobníkový automat)
kontextová: γAδ → γβδ
(automat s RAM, lineárn ohrani ený Turing v
Karel Richta
2
Sémantika programovacích jazyk : Syntaxe a sémantika stroj) neomezená: γAδ → α
(Turing v stroj, rekurzivn spo etné jazyky)
Bu γAδ → γβδ kontextové pravidlo. Vytvo íme-li gramatiku, která pro každé takové pravidlo bude obsahovat (bezkontextové) pravidlo A → β , pak z ejm jazyk generovaný touto gramatikou obsahuje všechny v ty p vodního kontextového jazyka. Libovolnou derivaci, která byla v p vodním jazyce provedena v kontextu γAδ, lze v nové gramatice provést rovn ž (bez ohledu na kontext). Bezkontextový nadjazyk navíc obsahuje i v ty, které vzniknou práv derivacemi bez ohledu na kontext. P .: Jazyk posloupností: A = { a }, L = A* P .: Jazyk binárních závorek: A = { a, b }, L = { anbn | n ≥ 1 } P .: Jazyk ternárních závorek: A = { a, b, c }, L = { anbncn | n ≥ 1 }
Syntaktické stromy Expr ::= Const | Var-Name | Expr + Expr
Nejednozna nost Expr ::= Const | Var | Expr + Expr Com ::= Var := Expr | if Expr then Com | if Expr then Com else Com
Abstraktní (syntaktické) stromy Jednozna nost bezkontextové gramatiky je nerozhodnutelná. Obecn je sice správn jší použít jednozna nou gramatiku, ale p i definici syntaxe asto využíváme nejednozna né gramatiky, nebo ty mohou být p ehledn jší. Musíme však vždy zajistit, aby nejednozna nost odvození nem la vliv na definici sémantiky. (1) Expr ::= Const (2) Expr ::= Var-Name (3) Expr ::= Expr + Expr Výraz "x + y + z" má r zná možná odvození (derivace): Expr -3-> Expr+Expr -2-> x+Expr -3-> x+Expr+Expr -2-> x+y+Expr -2-> x+y+z (3,2.1,3,2,2) Expr -3-> Expr+Expr -2-> Expr+z -3-> Expr+Expr+z -2-> x+Expr+z -2-> x+y+z (3,2.2,3,2,2) Abstraktní strom neobsahuje syntaktické detaily.
Regulární výrazy Mnoho jazyk má rekurzivní charakter v tom smyslu, že syntaktické kategorie jsou Karel Richta
3
Sémantika programovacích jazyk : Syntaxe a sémantika definovány rekurzivním odkazem na sebe sama: A → γAδ Pokud jsou γ i δ neprázdné et zce, m žeme je považovat za jakési závorky. Jazyky, které jsou generovány pomocí takových pravidel, obsahují tzv. závorkové struktury. Bezkontextové gramatiky jsou velmi vhodný nástroj práv na popis jazyk se závorkovými strukturami. Jazyky, které tuto vlastnost nemají, nazýváme regulární jazyky. T ída t chto jazyk zahrnuje mnoho zajímavých jazyk - asembler, p íkazový jazyk opera ního systému, atd. Regulární jazyk je jazyk, pro který existuje gramatika bez závorek. To neznamená, že by gramatika nemohla obsahovat rekurzi (levou nebo pravou). P .: Indentifikátory Id ::= Letter | Id Letter | Id Digit P .: Asembler Prog ::= e | Prog Instr Instr ::= Op Opnd
| Id Op Opnd
Op ::= LOAD | STORE | ADD | JUMP | ... Opnd ::= Id | Num Syntax regulárních jazyk lze popsat regulární gramatikou, ale asto používáme definici pomocí tzv. regulárních výraz . Bu A abeceda (kone ná neprázdná množina). Nech a ∈ A je libovolné písmeno abecedy. Zápisem [X] ozna íme množinu všech et zc , které zastupuje regulární výraz X. Množinu RE regulárních výraz (formální jazyk regulárních výraz ) nad abecedou A definujeme: Syntax: RE → e RE → a RE → RE · RE RE → RE | RE RE → RE* RE → (RE) Sémantika: RE
[ RE ]
poznámka
e
{e}
prázdný et z
a
{a}
znak
Karel Richta
4
Sémantika programovacích jazyk : Syntaxe a sémantika F·G
{ fg | f ∈ [F] ∧ g ∈ [G] }
z et zení
F|G
[F] ∪ [G]
varianta
F*
{ s 1…s k | s i ∈ [F] } ∪ { e }
iterace
(F)
[F]
skupina
P .: Syntax identifikátoru m žeme popsat regulárním výrazem: Dig = ( 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ) Lett = ( a | b | ... | Z ) Id = Lett · ( Lett | Dig )*
Mikrosyntaxe a makrosyntaxe Zápis v (programovacím) jazyce je tvo en posloupností znak abecedy, tj. L ⊆ A* . Pro ú ely definice jazyka je vhodné považovat za abecedu jazyka nikoliv jednotlivé znaky, ale tzv. lexikální elementy (lexémy, tokens) - identifikátory, literály, operátory, komentá e atd. Prvním krokem p i popisu jazyka je tedy definice syntaxe t chto lexém - mikrosyntaxe (lexikon) jazyka Q ⊆ A* . Programy pak považujeme za zápisy nad lexikonem jazyka Q, tj. L ⊆ Q* . Popis syntaxe pak nazýváme makrosyntaxe jazyka. P .: Jazyk D (triangle - dle Pascala) Mikrosyntax: Program ::= ( Token Comment Blank )* Token ::= Integer-Literal Character-Literal Identifier Operator Keyword Identifier ::= Letter · ( Letter | Digit )* ?? Identifier ::= Letter _ Identifier Digit Identifier Letter ... Makrosyntax: Program ::= Command Command ::= V-Name := Expression ... Expression ::= Literal V-Name Expression B-Operator Expression ... Karel Richta
5
Sémantika programovacích jazyk : Syntaxe a sémantika Zobrazení (p evod) lex: A* → Q* ∪ { error } se nazývá lexikální analýza a ídí se definicí mikrosyntaxe. asto se pro definici mikrosyntaxe používají regulární výrazy, pro makrosyntaxi se využívají obvykle bezkontextové gramatiky, BNF, EBNF, atd.
Bezkontextová gramatika a statická sémantika Popis kontextového jazyka pomocí bezkontextového nadjazyka a omezujících podmínek vyjád ených stejnými prost edky, jakými se popisuje sémantika - statická sémantika
Zp soby popisu sémantiky (dynamické sémantiky) opera ní sémantika, denota ní sémantika, axiomatická sémantika, ak ní sémantika Podle zp sobu definice: deduktivní sémantika (jazyková rovnost ur ena p ímo, interpretace nep ímo) axiomatická sémantika, p episovací systémy induktivní sémantika (interpretace ur ena p ímo, jazyková rovnost indukována interpretací) - denota ní sémantika Podle modelu: opera ní sémantika (význam je modelován výpo etní posloupností) funkcionální sémantika (jako model použity funkce) rela ní sémantika (jako model použity relace) kompila ní sémantika (jako model použit jiný jazyk)
Karel Richta
6
