hvis tager et eksempel program:
n := 4
a := n
old := 0
b := 1
while (a > b) and (a != old) do
begin
old := a
a := (a + b)/2
b := n/a
end
resultatet af programmet er at a vil være kvadratroden af n (jeg definerede godt nok ikke operatorerne før.
første skridt i pasningen kunne (og som regel er) at tokenize programmet, vi vil så her have følgende tokens:
ASSIGN, IF, THEN, ELSE, WHILE, DO, BEGIN, END, IDENTIFIER, EXPRESSION
tokenizer vi så vores program (evt. ekstra data angives med parantes) så får vi:
IDENTIFIER(n) ASSIGN EXPRESSION(4)
IDENTIFIER(a) ASSIGN EXPRESSION(n)
IDENTIFIER(old) ASSIGN EXPRESSION(0)
IDENTIFIER(B) ASSIGN EXPRESSION(1)
WHILE EXPRESSION((a > b) and (a != old)) DO
BEGIN
IDENTIFIER(old) ASSIGN EXPREESION(a)
IDENTIFIER(a) ASSIGN EXPRESSION((a+b)72)
IDENTIFIER(b) ASSIGN EXPRESSION(n/a)
END
kigger vi lidt på hvad de forskellige tokens svarer til i programkoden så får vi at
IF = "if"
THEN = "then"
ELSE = "else"
WHILE = "while"
DO = "do"
BEGIN = "begin"
END = "end"
disse kan så kaldes for reserverede ord
de resterende er
ASSIGN = ":="
IDENTIFIER = [a-z][a-z0-9]
EXPRESSION = ...
expression har jeg ikke fuldt defineret men jeg håber du har ideen.
vi har nu programmet parset op som en sekvens af tokens.
vi parser det nu igennem for at finde vores nonterminaler (dem der står på venstre side af vores grammatik)
hvis vi har med en assignment at gøre så har vi token mønstret IDENTIFIER ASSIGN EXPRESSION, og så er det blot at fodre vores assignment klasses konstruktør (i interpreter patternet) med ekstra dataene IDENTIFIER og EXPRESSION
Det bliver dog mere komplekst med de statements der kan indeholde andre statements, og således er rekursivt defineret, men det er dog ikke værre end det sagtens kan overkommes.
når du så med objekt referencer har fået opbygget dit syntax træ (for det er egentlig hvad det er), så siger du blot interpret, og dit script eksekveres.
her er wikipedia siden om interpreter patternet
http://en.wikipedia.org/wiki/Interpreter_patternog Dijkstra shunting yard (du behøves dog langtfra alt hvad den kan, kig nanvlig på muligheden for konvertering til rpn/postfix notation)
http://en.wikipedia.org/wiki/Shunting_yard_algorithmhttp://en.wikipedia.org/wiki/Shunting_yard_algorithm