GRAMMATON (top)

Grammaton is an artificial name put together from the word "GRAMMAr", "TOp" and "dowN" analysis, to name this project.

Format Requirements (top)

Rule: Each rule has to be typed in one line.

Context-free: There has to be only one nonterminal on the left-hand side, followed by the separator sign "=" and a sequence of nonterminals and / or terminals on the right-hand side. Alternative rules can be written with | - separator in one line.

correct rules:

IF = if EXPR the EXPR else EXPR fi
= STMT = IF | LOOP | ASSIGMENT
A =

incorrect rules:

if = - terminal symbol on the left-hand side
= abc - no symbol on the left-hand side
IF_STMT = if EXPR - three symbols on the left-hand side (the underscore is a terminal and not allowed here)

Please refer to the following grammar, which defines the syntax of a context- free rule. Nonterminals are written in upper case words, terminals marked with quotation marks "". The symbol = separates the side of rules and | defines alternative rules:

RULE = LEFTHANDSIDE "=" RIGHHANDSIDE
LEFTHANDSIDE = NONTERMINAL
RIGHTHANDSIDE = | ALTERNATIVE | ALTERNATIVE "|" RIGHTHANDSIDE
ALTERNATIVE = TERMINAL | TERMINAL ALTERNATIVE | NONTERMINAL | NONTERMINAL ALTERNATIVE
NONTERMINAL = (UPPERCASELETTER)+
TERMINAL = (LOWERCASELETTER | DIGIT | SYMBOL)+
UPPERCASELETTER = "A" | "B" | "C" | "D" | "E" |
"F" | "G" | "H" | "I" | "J" |
"K" | "L" | "M" | "N" | "O" |
"P" | "Q" | "R" | "S" | "T" |
"U" | "V" | "W" | "X" | "Y" |
"Z" | "À" | "Á" | "Â" | "Ã" |
"Ä" | "Å" | "Æ" | "Ç" | "È" |
"É" | "Ê" | "Ë" | "Ì" | "Í" |
"Î" | "Ï" | "Ð" | "Ñ" | "Ò" |
"Ó" | "Ô" | "Õ" | "Ö" | "Ø" |
"Ù" | "Ú" | "Û" | "Ü" | "Ý" |
"Þ"
LOWERCASELETTER = "a" | "b" | "c" | "d" | "e" |
"f" | "g" | "h" | "i" | "j" |
"k" | "l" | "m" | "n" | "o" |
"p" | "q" | "r" | "s" | "t" |
"u" | "v" | "w" | "x" | "y" |
"z" | "ß" | "à" | "á" | "â" |
"ã" | "ä" | "å" | "æ" | "ç" |
"è" | "é" | "ê" | "ë" | "ì" |
"í" | "î" | "ï" | "ð" | "ñ" |
"ò" | "ó" | "ô" | "õ" | "ö" |
"ø" | "ù" | "ú" | "û" | "ü" |
"ý" | "þ" | "ÿ"
DIGIT = "0" | "1" | "2" | "3" | "4" |
"5" | "6" | "7" | "8" | "9"
SYMBOL = "!" | """ | "#" | "$" | "%" |
"&" | "'" | "(" | ")" | "*" |
"+" | "," | "-" | "." | "/" |
":" | ";" | "<" | "=" | ">" |
"?" | "@" | "[" | "\" | "]" |
"^" | "_" | "`" | "{" | "}" |
"~" | "¡" | "¢" | "£" | "¤" |
"¥" | "¦" | "§" | "¨" | "©" |
"ª" | "«" | "¬" | "¯" | "®" |
"¯" | "°" | "±" | "²" | "³" |
"´" | "µ" | "¶" | "·" | "¸" |
"¹" | "º" | "»" | "¼" | "½" |
"¾" | "¿" | "×" | "÷"

Annotaion: Since the symbol "|" and blank are needed to write a grammar, they are not in the terminal set.
Please refer to The Unicode Standard, Version 4.0 to get each character's unicode.

Empty word: There is not a special character to represent the empty word. A rule derives the empty word, if it ends after "=" or if there exists an empty alternative as shown in the four examples.

1. A =
2. A = a | B |
3. A = a |   | B
4. A =   | a | B

Alternative rules separated by "|": You can enter alternative rules by separating them with "|". However, write them in one line, otherwise the grammar analysis will fail. During the analysis the program converts all alternatives into separate rules.

Whitespaces:

Doublets: It is allowed to insert equal rules. The program eliminates all doublets.

Format Requirements for the word to be parsed: Consecutive tokens in a word can be separated by at least one blank. However, use blanks carefully in a word, because they may affect its membership to the language defined by the grammar.
Given the grammar G = {{S, A}, {a, aa} {S = a A a, A = aa}, S}. The words "aaaa2 and "a aa a" belong to the language L of grammar G, but the word "aa aa" does not.

GRAMMATON user interface: (top)

1.) The initial Input Screen consists of the following components:

Menu: Located at the top of the main frame, it contains menu titles that describe the content of each menu.
File: Provides operations, such as clearing and closing the project.
Edit: Provides standard clipboard operations.
Examples: Provides some LL(k)-grammars and some faulty grammars, which are not suitable for the top down analysis.
Analysis: Provides operations to analyse the specified grammar and to parse the word.

Toolbar: This toolbar provides quick access to frequently used operations provided in the menu.

Pop up menu: This is an alternative way to access the operations under edit.

Two Tabs: This is where you switch between the input screen and the animation screen.

Grammar Editor: Allows you to view and edit your grammar.

Analyse Grammar Button: Analysis and checks your grammar for correctness.

2.) If any grammar is accepted to be LL(k) in the interval 1 <= k <= 10, the Input Screen changes its layout and the word editor appears beneath the grammar editor.

Word Editor: Allows you to view end edit the word which should be parsed.

Start Animation Button: Enables you to switch to the Animation Screen to have the parse process animated.

3.) The Animation Screen consists of the following components:

Grammar Animation Panel: Here you see the grammar rules. If there is any applied rule in that parse step, it will be highlighted.

Word Animation Panel: Shows the progress of the word acceptance. The word is broken into a sequence of tokens. A token could be

  • an accepted (green) token
  • the current (blue) token
  • a look ahead (blue) token
  • an unvisited (black) token
  • an error (red) token

Tree Animation Panel: Draws the derivation tree.

Legend Frame: Explains the meaning of the different colours.

Show Legend: Opens and close the legend window.

Controls to switch between the animation modes: This is where you switch from manual to automatical animation mode and vice versa.

Controls for manual animation mode: This is where you view the animated parse process step by step with the controls provided. It is also the default setting.

Controls for automatical animation mode: Here you watch the animated parse process like a film. Optionally, you can use this as an alternate to the manual mode.

Example: (top)

After loading, you see the Input Screen.

1. Insert your own grammar or load an example. Afterwards click the "Analyse Grammar" button or the equivalent menu item.

The result of the grammar inspection is presented. If the grammar is suitable for top down analysis a positive message box opens.

Or else, the current grammar is rejected and all errors are highlighted.

2. Press OK to close the dialog box again. The word editor appears only, if the grammar is valid, the word editor appears. Insert any word you want to parse and click "Start Animation" button or the equivalent menu item.

The program switches to the Animation Screen.

The first picture that is presented shows the initial parsing step. The animation mode is manual.

4. To watch the parse process, either click some manual controls or switch into automatically animation mode by selecting the appropriate radio button. At the end of the parse process a message box opens to inform whether it was successful or not.

5. Press OK to close the dialog box again. Play with the animation or click the tab "Input Pane" to return to the input screen. The grammar and the word are still readable.

Back to the Input Screen you can:

To terminate the program click the x-button in the upper right corner.