Syntax, syntaxträd, rekursiv medåkning

• Syntax för formella språk
• Rekursiv medåkning
• Syntaxkontroll med stack

Syntax för formella språk

Exempel: Språket som består av satserna JAG VET, JAG TROR, DU VET och DU TROR definieras av syntaxen

<Sats> ::= <Subj> <Pred>
<Subj> ::= JAG | DU
<Pred> ::= VET | TROR

I syntaxen ovan har vi tre omskrivningsregler. Varje regel består av ett vänsterled med en icke-slutsymbol (t ex <Sats> ovan) och ett högerled som talar om vad man kan ersätta vänsterledet med. I högerledet får det förekomma både icke-slutsymboler och slutsymboler (t ex JAG i exemplet ovan). Tecknet | betyder eller. Språket består av alla satser som kan bildas genom omskrivningar av startsymbolen <Sats>.

Meningar av typen
JAG VET ATT DU TROR ATT JAG VET OCH JAG TROR ATT DU VET ATT JAG TROR definieras nu så här:

<Mening> ::= <Sats> | <Sats><Konj><Mening>
<Konj>   ::= ATT | OCH

Syntaxen för programspråk beskrivs ofta i BNF. Så här kan man visa hur Javas tilldelningssatser ser ut:

<Assignment> ::= <Identifier> = <Expression> ;
<Identifier> ::= <Letter> | <Letter> <Digit> | <Letter> <Identifier>
<Letter>     ::= a-z | A-Z | _ | $
<Digit>      ::= 0-9

En kompilator fungerar ungefär så här:

 källkod --> lexikal analys --> syntaxanalys --> semantisk analys --> kodgenerering --> målkod

• Under en lexikal analys sållas oväsentligheter såsom blanktecken och kommentarer bort samtidigt som symboler vaskas fram.
• Syntaxanalysen (parsningen) kontrollerar att programmet följer syntaxen och skapar ett syntaxträd.
• Sen följer semantisk analys där kompilatorn ser efter vad programmet betyder.
• Sist sker kodgenerering där programmet översätts till målkod (t ex Java.class).

Rekursiv medåkning (recursive descent)

• läsSats()
• läsSubjekt()
• läsPredikat()
• läsMening()
• läsKonj()

class SyntaxAnalys{
    
    private Mio mio = new Mio();
    
    public void kontrolleraInmatning(){
	try {
	    läsMening();
	    mio.getLine();
	    System.out.println("Din mening följer syntaxen.");
	}
	catch(SyntaxErrorException e) {
	    System.out.println(e + " före " + mio.getLine());
	}
    } // kontrolleraInmatning()
    
    private void läsMening() throws SyntaxErrorException {
	    läsSats();
	    if (!mio.eoln()) {
		läsKonj();
		läsMening();
	    }
    } // läsMening()

    private void läsSats() throws SyntaxErrorException{
	läsSubjekt();
	läsPredikat();
    } // läsSats()

    private void läsSubjekt() throws SyntaxErrorException{
	String ord = mio.getWord();
	if (ord.equals("JAG") || ord.equals("DU"))
	    return;
	else
	    throw new SyntaxErrorException("Subjektfel");
    } // läsSubjekt()

    private void läsPredikat() throws SyntaxErrorException{
	String ord = mio.getWord();
	if (ord.equals("VET") || ord.equals("TROR"))
	    return;
	else
	    throw new SyntaxErrorException("Predikatfel");
    } // läsPedikat()

    private void läsKonj() throws SyntaxErrorException{
	String ord = mio.getWord();
	if (ord.equals("ATT") || ord.equals("OCH"))
	    return;
	else
	    throw new SyntaxErrorException("Konjunktionsfel");
    } // läsKonj()

} // class Syntax

public class SyntaxErrorException extends Exception {
    public SyntaxErrorException(String errorMessage){
        super (errorMessage);
    }
}//class SyntaxErrorException

Denna metod för syntaxanalys ska ni använda er av i extrauppgift 2. Programmet ska läsa in en matematikformel tecken för tecken och med rekursiv medåkning kolla syntaxen och utföra beräkningen. Parenteser, multiplikation, division, addition och subtraktion ska ingå.

Syntaxkontroll med stack

1. Skapa en tom stack
2. Slinga som läser symboler (här:tecken) tills inmatningen tar slut
   • Om symbolen är en vänsterparentes (t ex '{'), lägg den på stacken.
   • Om symbolen är en högerparentes (t ex '}'), titta på stacken. Om stacken är tom eller om den symbol som poppar ut inte matchar högerparentesen har vi ett syntaxfel.
3. När inmatningen tar slut - kolla om stacken är tom. Om den inte är tom har vi fått ett syntaxfel.

1. Letar parenteser att lägga på stacken. Övergår till tillstånd 2 om den upptäcker en kommentar, till tillstånd 3 om inmatningen tar slut.
2. Inuti kommentaren - läser bort tecken. Återgår till tillstånd 1 om kommentaren tar slut.
3. När inmatningen tar slut - kollar om stacken är tom. Om den inte är tom har vi fått ett syntaxfel.

Syntaxträd

Lösning:

     |
     *
   /   \
  2    ( )
        |
        +
      /   \
     3     *
         /   \
        4     5
          

<Uttryck> ::= <Term> | <Term> + <Uttryck> | <Term> - <Uttryck>;
<Term>    ::= <Faktor> | <Faktor> * <Term> | <Faktor> / <Term>;
<Faktor>  ::= TAL | -<Faktor> | (<Uttryck>);
          

    double readExpr() {
        // expr ::= term | term + expr | term - expr

        double x = readTerm();         // expr ::= term ...

        if (peek('+')) {               // expr ::= term + expr 
            popToken();
            x += readExpr();
        }                              // TODO expr ::= term - expr 

        return x;
    }

Det finns en ofärdig implemention här som man kan testa addition och multiplikation.