Programmēšanas valodas: Semantika Datorzinātnes pamati

Programmēšanas valodas: Semantika

• Datorzinātnes pamati

Semantikas definēšana: ievada apsvērumi

• Programmēšanas valoda – jēdzienu, konstrukciju kopums (sistēma), kas paredzēts programmu veidošanai (algoritmu aprakstam).

• Sintakse: programmu formēšanas un attēlošanas likumi (programmu kā instrukciju sistēmu veidošanas un pieraksta likumi)

• Semantika: saistība starp programmām kā instrukciju sistēmām un to izpildes laika diskrētajiem procesiem (kas notiek katras programmas izpildes laikā? Kāda ir valodas konstrukciju nozīme programmu izpildes laika terminos?)

• “Praktiskā” semantika: kā programma tiek izpildīta uz konkrētā datora?

• Konkrēts valodas L kompilators katrai programmai valodā L piekārto noteiktu ielādes moduli. Kompilators definē semantiku – atbilstību starp programmām un ielādes moduļiem (pieņemam, ka zinām, kādā veidā tiek izpildīts ielādes modulis).

• Kā secināt, ka otrs kompilators uz tā paša vai otra datora realizēs to pašu semantiku? – Vajadzīgs semantikas apraksts, kas ir neatkarīgs no konkrētā datora, konkrētā kompilatora.

• Papildus tam, cilvēks var gribēt arī rakstot programmu, zināt, kādā veidā tai būtu jādarbojas. – Vajadzīgs semantikas apraksts cilvēkam saprotamos terminos.

Semantikas apraksts: dabiskā vai formālā valodā?

• Semantika: saistība starp programmām kā instrukciju sistēmām un to izpildes laika diskrētajiem procesiem (kas notiek katras programmas izpildes laikā? Kāda ir valodas konstrukciju nozīme programmu izpildes laika terminos?)

• Semantikas apraksts: - neatkarīgs no konkrētās implementācijas, - cilvēkam saprotamos terminos.

• Semantikas apraksts dabiskā valodā, papildus izmantojot shematisku notāciju, balstoties uz intuīciju par diskrēto procesu izpildi – bieži vien var būt pietiekams, lai programmēšanas valodu lietotu (rakstītu programmas, u.c.).

• Matemātiski precīza valodas semantikas definīcija vajadzīga:

• - lai varētu matemātiski precīzi spriest par programmu īpašībām (analizēt programmas, pierādīt programmu īpašības), ja semantika ir precīza, programma kļūst par matemātisku objektu.

• - lai varētu implementēt (realizēt) programmēšanas valodu (uzrakstīt tai kompilatoru, interpretatoru, u.c.) , veidot vidi, kurā citi var rakstīt programmas šajā valodā un tās izpildīt. - …

Programmēšanas valodu semantikas uzdošana

• Matemātiski precīza semantika saista katru programmu ar noteiktu matemātisku objektu, kas “labi” raksturo šīs programmas realizēto diskrēto procesu.

• Kādi ir šie matemātiskie objekti?

• Iespējas ir dažādas (šeit daži piemēri):

• Paplašināts automāts, abstrakta mašīna, stāvokļu pāreju grafs, u.taml. (operacionālā semantika)

• Funkcija, kas raksturo programmas izejas datu atkarību no ieejas datiem (denotacionālā semantika)

• Attiecība starp programmas ieejas un izejas datiem (dabiskā semantika)

• Matemātiska teorija, kas satur visus noteiktā loģiskā valodā pierakstāmos apgalvojumus, kas ir patiesi attiecībā uz konkrēto programmu (aksiomātiskā semantika)

• Algoritms, kas katrai programmai dotajā valodā piekārto kādu programmu citā valodā, kuras semantika jau ir zināma (translatīvā semantika)

• Vienai valodai var būt vairākas semantikas (tad gan vajadzīgi “saskaņotības” pierādījumi starp tām).

Mainīgo stāvokļa jēdziens

Abstraktā sintakse Programmu struktūras uzdošana

Semantikas definējums: izteiksmes Attēls: x + (y * 3)

Komandu izpilde: dabiskā semantika

Dabiskās semantikas izveduma piemērs

Determinitātes teorēma

Determinitātes teorēma: pierādījuma komentāri

Komandu izpilde: operacionālā semantika

Operacionālās semantikas izveduma piemērs

Semantiku atbilstība (A)

Semantiku atbilstība (B)