Nada

Föreläsning 6: Syntax, automater och XML

Sekvensdiagram

Hittills har vi bara använt klassdiagram som visar hur klasserna hänger ihop och ibland hur många objekt det finns av varje klass. Om man vill visa körningens tidsförlopp ritar man sekvensdiagram (s 69-71). Tiden går neråt, varje objekt är en vertikal linje. Var den metod som för tillfället körs ligger visas genom att den objektlinjen förtjockas. Anrop av metod i annat objekt blir en vågrät pil och när metoden gör return går en streckad pil tillbaka.

Anropa operativsystemet

Sekvensdiagram är intressantast när flera trådar är aktiva samtidigt. En process som alltid finns samtidigt som javaprogrammet är förstås operativsystemet och det är ofta intressant för javaprogrammet att kunna anropa operativsystemet, så som användaren kan göra genom att skriva kommandon i Unix eller genom att klicka på ikoner i Windows.

För att ett program ska kunna anropa operativsystemet behövs ett API (application programmer's interface), dvs en uppsättning anrop. Det finns i javabibliotekets klass Runtime (som inte kräver någon import) och så här gör man.

class SuddaDum                                             {
  public static void main(String[] args)                   {
    try{Runtime.getRuntime().exec("rm Dum")                ;}}
    catch(Exception e){System.out.println(e)               ;}}}
Fabriksmetoden getRuntime tillverkar ett objekt med en enda intressant metod exec och till den kan man skicka valfria kommandon. Om det finns någon fil Dum kommer den att suddas.

Vanligen ger man inte kommandon direkt till operativsystemet utan via ett användarvänligt kommandoskal (eng. shell). Det är detta shell som låter en använda jokertecknet stjärna i kommandon som rm *. Men det går lika bra att låta exec-metoden köra shell-programmet /bin/sh och skicka med kommandoraden som parameter, så här.

class SuddaAllt                                            {
  public static void main(String[] args)                   {
    String[] kommando = {"/bin/sh", "-c","rm *"}           ;
    try{Runtime.getRuntime().exec(kommando)                ;}}
    catch(Exception e){System.out.println(e)               ;}}}
Det är alltså katastrofrisk om man kör ett okänt javaprogram på sin dator!!! Som tur är har Java ett hjälpmedel för att skydda en när man kör skumma program. I Javamaskinen finns en sur gubbe som heter java.security.manager och när han är inkallad stoppar han alla farligheter såsom filhantering, nätförbindelser och åtkomst till högtalare, skrivare etc. Så här blir det säkra körkommandot.
java -Djava.security.manager SuddaAllt
Med -D sätter man önskade systemparametrar för körningen. Man kan också tala om för surgubben att han ska tillåta vissa saker, och det gör man i en policy-fil. Låt oss anta att filen bra.policy innehåller en enda rad.

grant{permission java.security.AllPermission;};

Då skulle security managern i alla fall tillåta suddningen om vi startar programmet med
java -Djava.security.manager -Djava.security.policy=bra.policy SuddaAllt
Men det går förstås att tillåta endast filläsning.

Syntax

Ett formellt språk är en väldefinierad uppsättning textsträngar, till exempel alla månadsnamn eller alla Java-program. Det bästa sättet att definiera ett språk är med en syntax (observera betoning på sista stavelsen!), det vill säga en grammatik. En så kallad kontextfri grammatik kan beskrivas i Backus-Naur-form (BNF).

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
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 | Identifier Digit | Identifier Letter
Duger denna syntax eller behöver den förbättras?

En kompilator måste bland annat kontrollera att programmet följer syntaxen. Med syntaxen i BNF visar sej detta vara oväntat enkelt.

Automater för syntaxanalys

Ett program som läser en datafil och antingen godkänner eller underkänner den brukar man kalla en automat. En portkodsautomat är ett känt exempel.
Sats: För varje automat kan man med BNF-syntax beskriva vilka teckenföljder som blir godkända.
Satsen är inte självklar eftersom det kan finnas oändligt många sådana teckenföljder men syntaxen är ändlig. Vi ska se hur man tillverkar en automat från BNF-syntaxen. Metoden heter rekursiv medåkning (recursive descent).
För varje symbol i grammatiken skriver man en inläsningsmetod. Om vi vill analysera grammatiken ovan behöver vi alltså metoderna: Flergrenade definitioner kräver tjuvtitt med Mio.nextChar(). När något strider mot syntaxen låter vi ett särfall skickas iväg. Här följer ett program som undersöker om en mening följer syntaxen ovan.
class Syntaxkoll                                  {
    
  static void läsMening() throws Exception        {
    läsSats()                                     ;
    if(!Mio.eoln())                               {
      läsKonj()                                   ;
      läsMening()                                 ;}}

  static void läsSats() throws Exception          {
    läsSubjekt()                                  ;
    läsPredikat()                                 ;}
      
  static void läsSubj() throws Exception          {
    String ord = Mio.getWord()                    ;
    if(ord.equals("JAG")) return                  ;
    if(ord.equals("DU"))  return                  ;
    throw new Exception("Fel subjekt:"+ord)       ;}

  static void läsPred() throws Exception          {
    String ord = Mio.getWord()                    ;
    if(ord.equals("TROR")) return                 ;
    if(ord.equals("VET"))  return                 ;
    throw new Exception("Fel predikat:"+ord)      ;}

  static void läsKonj() throws Exception          {
    String ord = Mio.getWord()                    ;
    if(ord.equals("ATT")) return                  ;
    if(ord.equals("OCH")) return                  ;
    throw new Exception("Fel konj:"+ord)          ;}

  public static void main(String[] args)          {
    System.out.print("Skriv en mening: ")         ;
    try                                           {
      läsMening()                                 ;
      System.out.println("Följer syntaxen!")      ;}
    catch(Exception e)                            {
      System.out.println(e+" före "+Mio.getLine());}}}
Om syntaxen skrivits så att alla rekursiva anrop kommer på slutet (som för symbolen Mening i vårt exempel) klaras kollen av en ändlig automat. Om den är skriven olämpligt kan man ofta skriva om den slutrekursivt (så är det med symbolen Identifier). Men går inte det behövs det i allmänhet en stack som arbetsminne, och eftersom en stack kan växa sej hur stor som helst är då inte automaten ändlig längre.

XML - taggade textfiler

Vilket datum skrivs 03/02/01? Det finns minst tre vanliga tolkningar: andra mars förra året, tredje februari förra året och första februari nästa år. Så här är det med alla data: dom kan tolkas olika om ingen beskrivning följer med. XML är ett sätt att förse data med taggar som talar om vad dom betyder. Så här skulle ett upptaggat datum kunna se ut.
<Date>
   <Year>2001</Year>
   <Month>02</Month>
   <Day>03</Day>
</Date>
På motsvarande sätt kan alla tänkbara datafiler taggas upp. Vilka ord som helst får användas i starttagg och tillhörande sluttagg, därav namnet eXtensible Markup Language. Bland tidigare taggspråk med en fix uppsättning taggar är HTML mest känt (HyperText Markup Language). Där anger taggarna inte vad data betyder utan hur text ska se ut.
Här kommer <B> text med fetstil </B>
och här lite <I> kursiverad text</I>
Data som bara består av ett eller ett par ord behöver man inte kosta på start och sluttagg. Dom kan i stället vara attribut inne i starttaggen, som framgår av följande fullständiga XML-fil.
<?xml version="1.0"?>
<Date year="2001" month="02" day="03">
   <Name>Disa</Name>
   <Name>Hjördis</Name>
   <Moon phase="full"></Moon>
</Date>
Det hör till god stil att ha med den första kommentarraden och att ge filen namn av typen date.xml.

DTD - beskrivning av XML-dokument

För att upptaggade datafiler ska kunna behandlas automatiskt måste man komma överens om vilka taggar som ska förekomma osv. Det här beskrivs i en DTD-fil (som kan stå för dokumenttypdefinition). I vårt exempel skulle filen date.dtd kunna se ut så här.
<!DOCTYPE Date [
   <!ELEMENT Date (Name*, Moon?)>
   <!ATTLIST Date year    CDATA #REQUIRED>
   <!ATTLIST Date month   CDATA #REQUIRED>
   <!ATTLIST Date day     CDATA #REQUIRED>
   <!ATTLIST Date weekday CDATA #IMPLIED>
   <!ELEMENT Name (#PCDATA)>
   <!ELEMENT Moon EMPTY>
   <!ATTLIST Moon phase (new|between|full) "between">
]>
Ett element är avsnittet från en starttagg till tillhörande sluttagg. Ett Date-element ska bestå av ett valfritt antal Name-element, och eventuellt ett Moon-element. Om stjärnan varit ett plustecken hade det betytt minst ett Name-element.
Fyra olika attribut kan finnas i Date-starttaggen; dom tre första obligatoriska (#REQUIRED) och det sista frivilligt (#IMPLIED). Mellan Name-taggarna får det stå valfri text (#PCDATA) men mellan Moon-taggarna får det inte stå någonting (EMPTY). Månens fas måste vara något av orden new, between, full och om inget Moon-element finns med antas between gälla.

Om man vill kan man lägga in DTD-beskrivningen i XML-filen, omedelbart efter överskriftsraden. Annars lägger man in en hänvisningsrad:

<!DOCTYPE Date SYSTEM "date.dtd">
Många grupper håller på att standardisera DTD-filer för till exempel musik, kemi och matematik. Dessa standarder antas vara kända för alla XML-läsande program, och då byter man ut SYSTEM mot PUBLIC.

Java-hjälpmedel för XML

Javaklasser som behandlar XML-filer finns ännu inte med i Javas standardbibliotek men kan laddas ner från http://www.java.sun.com/xml. Två olika arbetssätt finns. SAX är snabbt och effektivt men allt kan inte göras rekursivt, i farten medan man analyserar filen, och när den är genomläst kan man inte gå tillbaka. DOM är trögt och minneskrävande men nödvändigt för mera komplicerat arbete med filen (eller om man är dålig på rekursion).
Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 4 februari 2004
Tekniskt stöd: <webmaster@nada.kth.se>