| 10:35a |
Visual Language Theory (Marriott and Meyer)
Currently there are three main aproaches to the specification of visual languages: the grammatical approach, the logical approach, and the algebraic approach.
Grammatical formalizms rewrite sets of mltisets (rather than sequences as in string languages) and specify geometric relationships between objects to be rewritten (Kirsch, 1964)
Logical approach uses first-order mathematical logic or other forms of mathematical logic, which often stem from artificial intelligence and axiomatize different possible topoligical relationships between objects. Same formalizm can be used for both the syntax and the semantics of a diagram.
Algebraic specification consists of composition functions, which construct complex pictures from simpler picture elements. Parsing is finding a function sequence that constructs the picture. Semantics is handled by defining parallel algebraic specifications for the diagrams and application domain and providing morphisms between their signatures.
Grammatical formalizms are computationally tractable parts of the logical or algebraic specifications. |
| 12:08p |
String languages
(from Marriott & Meyer)
Following Chomsky the syntax of sequantial languages is specified using a phrase-structure grammar.
Grammars are production rules describing composition of the grammatical components (sentences or noun phrases).
Example: English sentence (S) consists of a noun phrase (NP) followed by a verb phrase (VP). NP consists of a noun (N) preceded by optional article or determiner (D) and adjectives (A). VP consists of a verb (V) followed by NP. This definition for a subset of English with N, A, V, D is captured by production rules:
S -> NP VP,
NP -> D NP2
NP2->A NP2
NP2-> N
VP -> V NP
D -> the/a
N -> dog/dinner
V -> eats
A -> happy/black
Thus "The happy dog eats dinner" is syntactically valid sentense since it can be furnished a derivation: that is recursive application of a production rule to replace the right-hand side of a prodution by the left-hand side.
terminal symbols: real words (dog, eats) and non-terminal symbols: grammar categories (N, P,..) S- is a start non-terminal symbol.
The set of sentences, which may by produced from S in the grammar using productions in the grammar is language of the grammar.
Membership problem: is a sentence in the language of the grammar? is solved by a parser, which will or will not produce a derivation like above. |