Understanding Interpreters and Grammar Structures
Explore the concept of interpreters in programming languages, including motivation, language interpretation, grammar rules, and symbol table structures. Learn about abstract syntax trees, expression interpretation, and simple grammatical examples. Enhance your knowledge of object-oriented, runtime, and object structures related to grammar representations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Interpreter Motivace Interpretace jazyka Gramatika Regul rn / booleovsk v razy, parsov n XML, ... Obecn e en Vytvo me interpret tohoto jazyka Forma abstraktn ho syntaktick ho stromu Interpretace v ty jazyka = e en dan instance probl mu
Obecn struktura symbol table interpreter symbol number / variable operators
astnci AbstractExpression Deklaruje abstraktn metodu Interpret() TerminalExpression Implementuje metodu Interpret() asociovanou s termin lem gramatiky Instance pro ka d termin ln symbol ve vstupu NonterminalExpression Implementuje metodu Interpret() netermin lu gramatiky T da pro ka d pravidlo gramatiky Udr uje instance prom nn ch typu AbstractExpression pro ka d symbol Context Udr uje glob ln informace Client Vytvo abstraktn syntaktick strom reprezentuj c konkr tn v tu jazyka slo en z instanc NonterminalExpression a TerminalExpression Vol metodu Interpret()
Jednoduch gramatika P klad: Gramatika regul rn ho v razu expression ::= literal | alternation | sequence | repetition | '(' expression ')' alternation ::= expression '|' expression sequence ::= expression '&' expression repetition ::= expression '*' literal ::= { 'a' | 'b' | 'c' | ... }* Pou it raining & (dogs | cats)*
Objektov struktura Gramatika regul rn ho v razu expression ::= literal | alternation | sequence | repetition | '(' expression ')' alternation ::= expression '|' expression sequence ::= expression '&' expression repetition ::= expression '*' literal ::= 'a' | 'b' | 'c' | ... { 'a' | 'b' | 'c' | ... }* Objektov struktura T da pro ka d pravidlo gramatiky Instance reprezentuj podv raz Symboly jsou v prom nn ch
Runtime reprezentace Gramatika regul rn ho v razu expression ::= literal | alternation | sequence | repetition | '(' expression ')' alternation ::= expression '|' expression sequence ::= expression '&' expression repetition ::= expression '*' literal ::= 'a' | 'b' | 'c' | ... { 'a' | 'b' | 'c' | ... }* Abstraktn syntaktick strom tvo en instancemi t d Reprezentace regul rn ho v razu raining & ( dog | cats ) *
Postfixov kalkulaka V raz 9 8 7 - + Stromov reprezentace Algoritmus Vytvo it pr zdn z sobn k Vytvo seznam token rozd len m vstupn ho et zce podle mezer Pro ka d token Pokud je symbol slo, p idej do z sobn ku Pokud je symbol operator vyt hni ze z sobn ku sla a aplikuj operator v sledek oper toru vra do z sobn ku Pokud je v raz p e ten bez chyb a v z sobn ku je pouze jedna hodnota v sledek
Terminal expression interface Expr { int interpret(); } class NumberExpr : Expr { int number; NumberExpr(int number){ this.number = number; } NumberExpr(String number){ this.number = parseInt(number); } override int interpret(){ return this.number; } }
Nonterminal expression class AddExpr : Expr { Expr Expr1, Expr2; AddExpr( Expr Expr1, Expr Expr2){ this.Expr1 = Expr1; this.Expr2 = Expr2; } override int interpret(){ return Expr1.interpret() + Expr2.interpret(); } } class SubExpr : Expr { .... } bool isOperator( String symbol) { return symbol == "+" || symbol == '-'; Expr getExprObject( Expr Expr1, Expr Expr2, String symbol) { if( symbol == "+") return AddExpr( Expr1, Expr2); else if( symbol == "-") return SubExpr( Expr1, Expr2); }
Parser class ExpressionParser { Stack stack; int parse(String str){ String[] tokenList = str.split(" "); for( String symbol : tokenList) { if( isOperator( symbol)) { Expr Expr1 = stack.pop(); Expr Expr2 = stack.pop(); Expr operator = getExprObject( Expr1, Expr2, symbol); stack.push( NumberExpr( operator.interpret()); } else /* isNumber */ { Expr numberExpr = NumberExpr(symbol); stack.push(numberExp); } } int result = stack.pop().interpret(); return result; } }
Sousti vzoru Vzor obsahuje: Gramatiku Popisuj c jazyk, v n m budeme p ij mat instance probl mu Co nejjednodu Reprezentaci gramatiky v k du T da pro ka d pravidlo gramatiky Abstraktn p edek D di nost odpov d gramatice Reprezentaci kontextu interpretace Vzor neobsahuje: Parser pro konstrukci syntaktick ho stromu instance probl mu
Vyhodnocen booleovskch vraz Pr ce s booleovsk mi v razy BooleanExp ::= Variable | Constant | OrExp | AndExp | NotExp | '(' BooleanExp ')' AndExp ::= BooleanExp 'and' BooleanExp OrExp ::= BooleanExp 'or' BooleanExp NotExp ::= 'not' BooleanExp Constant ::= 'true' | 'false' Variable ::= 'A' | 'B' | ... | 'Z' (true and x) or (y and (not x)) interface BooleanExp { bool interpret(Context context); }; spole n rozhran definuj c booleovsk v raz class Context { bool lookup(String name); void assign(VariableExp exp, boolean bool); }; mapov n prom nn ch na true a false implementace nen sou st n vrhov ho vzoru
Promnn a konstanty Reprezentace Variable class Variable : BooleanExp { String name; Variable(String name){ this.name = name; }; ohodnocen e context boolean interpret(Context context){ return context.lookup(name); } }; Reprezentace Constant class Constant : BooleanExp { boolean bool; Constant(boolean bool){ this.bool = bool; }; boolean interpret(Context context){ return bool; } };
Opertory Reprezentace AndExp ::= BooleanExp 'and' BooleanExp class AndExp : BooleanExp { BooleanExp operand1; BooleanExp operand2; AndExp(BooleanExp op1, BooleanExp op2){ operand1 = op1; operand2 = op2; }; boolean interpret(Context context){ return operand1.interpret(context) && operand2.interpret(context); }; }; Obdobn OrExp a NotExp
Instance a interpretace Context context; Variable x = new Variable("X"); Variable y = new Variable("Y"); vytvo en AST pro v raz (true and x) or (y and (not x)) BooleanExp expression = new OrExp( new AndExp( new Constant(true), x), new AndExp( y, new NotExp(x)) ); context.assign( x, false); context.assign( y, true); ohodnocen prom nn ch boolean result = expression.intepret(context); interpretace pro konkr tn ohodnocen
Souvisejc vzory Composite Nej ast j kombinace Struktura stromu je implementace Composite Visitor Podobn zp sob proch zen stromu Odd lena funkcionalita od dat M e nejen vypo t vat n jakou hodnotu, ale i data transformovat Iterator Proch zen strukturou D le it spole n abstraktn p edek Flyweight Typick pro p eklada e Sd len konstantn ch v raz vyhodnocovan ch v compile-time
Shrnut Typick pou it "Parsery", "kompil tory", "interpretry" velmi jednoduch Omezen pou itelnosti Jednoduch gramatika Slo it j gramatiky nep ehledn k d, exploze t d Jin n stroje - Bison, Yacc, ... Efektivita nen kriticky d le it Jinak l pe nekonstruovat syntaktick strom stavov automat V hody Lehce roz i iteln / zm niteln gramatika Jednoduch implementace gramatiky P id v n dal ch metod interpretace Nev hody Slo it gramatika t ce udr ovateln prakticky nepou iteln
