Lägesrapport

Inget speciellt att rapportera, jag tänkte bara meddela att min TW-krönika som förespråkar skadeståndsansvar för vårdslös programmering nu finns tillgänglig – minnesgoda läsare känner igen temat från ett tre år gammalt inlägg.

Men när jag ändå har textarean framme kan jag meddela att kursen i nationalekonomi har varit jätteintressant, men att examineringen nu på fredag verkar bli rätt trist – för att svara på frågorna krävs inte något eget tänkande, men däremot en hel massa noggrannhet och detaljer. Säkert bra för vissa, men dåligt för en kreativ slarver som mig. Och vad är grejen med att det förväntas att juriststudenter ska ogilla/vara dåliga på matte?

Arbetet på lagen.nu 1.5 går vidare – jobbet med tabelligenkänningskoden jag skrev om sist har gått ganska bra. Ett enkelt exempel är att den här plaintexten tolkas som den här tabellstrukturen. Ett lite knepigare är den här texten som blir den här strukturen. Det senaste jag jobbat med är hanteringen av referenser i löpande text – något jag också skrev om för tre år sedan, men det nya är att koden modulariserats så att man kan ha en grammatik för vanliga svenska lagtexter, en för typiska förarbetshänvisningar, en för EG-lagstiftning osv, och vid instansieringstillfället välja vilken eller vilka grammatiker man vill använda.

På söndag ska jag springa premiärmilen och hoppas få en tid nedåt 45 minuter, eller i vart fall inte mer än 50. Vi får väl se. De senaste veckorna har jag bara sprungit 12- och 21-kilometersrundor (fartleks– och LSD-pass, respektive), så det ska bli kul att köra ett plattan-i-mattan-rejs.

Jack of all trades, master of none

För att bygga lagen.nu 2.0 kommer det krävas ett rätt stort lass med teknologier. Jag har väl ungefär samlat ihop alla pusselbitar och känner mig ungefär som när man storhandlat inför en riktigt ambitiös middagsbjudning — alla råvaror och alla verktyg finns på plats, nu gäller det bara att hantera dem. Lite om vad som ingår:

XML: Lagen.nu 1.0 använde XML en hel del bakom kulisserna, men XML-formaten var odokumenterade, ad-hoc’iga och i största allmänhet inte så väldigt XMLiga (inga namespaces, data som borde varit i noder lagrades i attribut och vice versa, inget utnyttjande av befintliga standarder som RDF och XLink). Det här ska på något sätt bli bättre i 2.0 — det finns en hel del internationella projekt kring hur juridisk information ska representeras i XML, men de flesta känns som kommittéprodukter med mycket snack och lite spec — det känns som XML inbjuder till sånt, i högre grad än andra komponenter i stacken nedan. Metalex verkar dock lovande.

XSLT: För att få ut de semantiskt korrekta XML-dokumenten på webben måste de transformeras till nån sorts HTML. För 1.0 gjorde jag en del riktigt knepiga transformationer då mantrat där var ”vem behöver databaser när vi kan slänga in allt i ett gigantiskt XML-dokument och XPath()a oss fram” — för 2.0 kommer en vanlig old-school relationsdatabas att användas, så förhoppningsvis blir det bara en fråga om att ta befintliga stylesheets och trimma lite.

SOAP: Det här är väl mera på nice-to-have-listan snarare än release-blocker-listan, men det vore kul att åtminstone doppa tårna i hela webservicesträsket. Två problem är dock att jag aldrig har jobbat mot någon skarp web service från klientsidan, så jag vet inte riktigt hur ett WS-API ska kännas för att vara bra, samt att jag egentligen inte har en bra känsla för vilka rättskälleinformationsfunktioner som skulle vara vettiga att göra åtkomliga som webservices.

HTML: Allt ska ju bli HTML till slut, så viss koll på läget måste jag ju ha även här. Det blir förmodligen XHTML 1.0 Strict, en viss grad av divitis (den lösning jag skissade på här visade sig vara ohållbar när man kör den på exempelvis inkomstskattelagen och många kommentarer), och förmodligen tyvärr sämre semantisk meningsfullhet än i 1.0 (det största problemet är numrerade listor — för att sätta en kommentar bredvid en punkt i en punktlista kan jag inte representera själva punkten som en LI-tag — det går inte att placera en P-tag med kommentaren vid sidan av när man är i ett UL-kontext). Dock så ska ett flertal tabeller bort och ersättas med DL-listor, efter tipsen här.

CSS: Ärligt talat är inte 1.0 särskilt visuellt upphetsande. Det kanske inte kommer bli pastellfärger och rundade hörn, men en något mer genomtänkt visuell känsla hoppas jag kunna åstadkomma. Jag har med min nya op-center-setup möjlighet att testa på Firefox, IE, Konqueror, Opera och Safari, och ser med skräckblandad förtjusning fram emot utmaningen att få det hela att se bra ut utan att degenerera till tabellsoppa.

DHTML/AJAX: Inte bara för att det är en nödvändig beståndsdel om man vill vara web 2.0, mycket av wikifunktionaliten skulle vinna på att med lite AJAX göra det möjligt att redigera kommentarer rakt på sidan, a la flickr‘s fotobeskrivningsmagi. Och vore det inte coolt om sökrutan föreslog lagtexter a la google suggest? Jag har kollat runt på vad för hjälpramverk som finns på javascriptutvecklingsscenen (jag har läst DHTML Utopia och såg inte alls fram enmot att göra all crossbrowserkompatibilitetssörja för hand) och fastnade tillslut för MochiKit (efter att ha kollat på Dojo, Prototype/script.aculo.us, YUI och den här artikeln) — att det beskrevs som kraftigt pythoninfluerat var ett tungt vägande skäl.

EBNF: En av de bästa sakerna med lagen.nu 1.0 var den EBNF-baserade tolkningen av lagtextreferenser i löpande text. Den är, i ärlighetens namn, mest ihophackad utan någon djupare förståelse för textparsning i den högre skolan, och det känns som att jag borde ägna lite tid åt SimpleParse-dokumentationen för att hantera andra typer av referenser, nu när jag ska hantera flera typer av rättskällor.

Python: Jag hamnar ofta i fällan att när jag, när jag lärt mig ett verktyg tillräckligt bra för att få riktigt jobb gjort med det, slutar lära mig mera. Under våren har jag dock gått tillbaks till grunderna för python och försökt utnyttja mer än de få procent av språket som 1.0 använder. Det blir vettig objektorientering, bättre utnyttjande av standardbiblioteket och kanske lite riktigt funktionell programmerings-tänk (första kapitlet i TPiP är en riktig ögonöppnare här). De tre viktigaste bitarna kommer nog bli Django för allt dynamiskt, BeautifulSoup för allt HTML-tröskande (tillsammans med SimpleParse enligt ovan), och ElementTree för allt XML-byggande.

MySQL: Och så ska ju saker lagras i en databas också. Jag är som tidigare nämnts skeptisk mot RDBMS-användande, men med tanke på hur fint django abstraherar bort det hela känns det motiverat att faktiskt plocka in en databasserver i mixen. Det blir förmodligen MySQL även om alla de coola kidsen använder Postgresql, men då jag redan har en MySQL-server körandes för WordPress, MediaWiki och lite annat, har jag än så länge inte sett nån verklig anledning att byta.

Ungefär så — det blir en ganska diger lista när man kollar på den. Vilket anknyter till den här bloggpostningens titel, det kan inte bli några djupa kunskaper inom varje enskild del (särskilt som en stor komponent inte är med här, nämligen domänkunskapen om just rättsinformation) men förhoppningsvis tillräckligt för att ro det hela i land.

Part 5: Finding and formatting inline law references

(Earlier posts: 1, 2, 3, 4)

The second part of the convert-things-to-xml approach deals with
finding inline references to other paragraphs in the law
text. I’ve written about it in part in this
blog post
, but to recap:

Swedish law text contains lots and lots of internal and external
references to other sections. These references have a
semi-standardized format, but they are clearly meant to be parsed
by humans, not machines.

The simplest case is a single reference to a single section
(example from 4 §
Försäkringsrörelselagen (1982:713)
):

    Vid ändring av en bolagsordning eller av en beviljad koncession
    gäller 3 § i tillämpliga delar.
  

Here, the string ‘3 §’ signifies a reference to the third section
in the current section of the current law. If we can identify and
mark that reference up, we can make the ‘3 §’ into a hyperlink
leading to the definition of section 3. You know, the stuff
hyperlinking was designed for. Currently, this gets transformed
into the following XML (how the XML gets transformed into
clickable HTML is the subject of a later article):

    Vid ändring av en bolagsordning eller av en beviljad koncession
    gäller <link section="3">3 §</link> i tillämpliga delar.
  

For cases like that, the transformation is trivial, and could be
done with regexps or just simple string matching. But for cases
like this (Patentbesvärsrätten
96-837
):

    14 § 1 st. 6) och 6 § varumärkeslagen (1960:644)
  

or better yet, this (49
a § URL
, my personal favourite):

    Bestämmelserna i 2 § andra och tredje styckena, 3, 7--9 och 11 §§,
    12 § första stycket, 13, 15, 16, 18--20 och 23 §§, 24 § första
    stycket, 25--26 b, 26 d -- 26 f, 26 i -- 28, 31--38, 41, 42 och
    50--52 §§ skall tillämpas på bilder som avses i denna paragraf.
  

things get way more complicated. Enter EBNF-grammar-based parsing
with the dynamic duo that is SimpleParse and mxTextTools. Also,
the book Text Processing in
Python
by David Mertz should be mentioned, as it helped me in
the right direction when I realized regexes weren’t going to cut
it.

My previous
post
describes the actual EBNF grammar and how SimpleParse is
used to build a parse tree from it, so you might want to read that too.

However, that is really only half of the problem. After having a
tree of parsed tokens, that might (for a somewhat complicated
scenario) look like the following:

refs': '14 § 1 st. 6) och 6 § varumärkes|lagen (1960:644)'
    'ExternalRefs': '14 § 1 st. 6) och 6 § varumärkes|lagen (1960:644)'
        'MultipleGenericRefs': '14 § 1 st. 6) och 6 §'
            'GenericRefs': '14 § 1 st. 6)'
                'GenericRef': '14 § 1 st. 6)'
                    'SectionPieceRef': '14 § 1 st. 6)'
                        'SectionRef': '14 §'
                            'SectionRefID': '14'
                                'number': '14'
                            'Whitespace': ' '
                        'Whitespace': ' '
                        'PieceRef': '1 st. 6)'
                            'PieceRefID': '1'
                                'ordinal': '1'
                            'Whitespace': ' '
                            'PieceOrPieces': 'st.'
                            'Whitespace': ' '
                            'ItemRef': '6)'
                                'ItemRefID': '6'
                                    'number': '6'
                                'RightParen': ')'
            'WAndOrW': ' och '
                'Whitespace': ' '
                'AndOr': 'och'
                    'And': 'och'
                'Whitespace': ' '
            'GenericRefs': '6 §'
                'GenericRef': '6 §'
                    'SectionRef': '6 §'
                        'SectionRefID': '6'
                            'number': '6'
                        'Whitespace': ' '
        'Whitespace': ' '
        'ExternalLawRef': 'varumärkes|lagen (1960:644)'
            'NamedExternalLawRef': 'varumärkes|lagen (1960:644)'
                'word': 'varumärkes'
                'Pipe': '|'
                'LawSynonyms': 'lagen'
                'Whitespace': ' '
                'LawRef': '(1960:644)'
                    'LeftParen': '('
                    'LawRefID': '1960:644'
                        'digit': '1'
                        'digit': '9'
                        'digit': '6'
                        'digit': '0'
                        'Colon': ':'
                        'digit': '6'
                        'digit': '4'
                        'digit': '4'
                    'RightParen': ')'
  

, how do we turn it into the following XML?

    <link law="1960:644" section="14" piece="1" item="6">
      14 § 1 st. 6)
    </link>
    och 
    <link law="1960:644" section="6">
      6 §
    </link>
    varumärkes|lagen (
    <link law="1960:644">
      1960:644
    </link>
    )
  

Turns out this is a problem that can be solved in a rather generic
manner with a small amount of planning and a little
recursiveness. Basically, all tokens that end in ‘Ref
should generally end up formatted as a <link>. All
tokens underneath such tokens that ends in ‘RefID‘ are
used to find the attributes for these tags. Start at the root,
then recurse depth-first over all child nodes until
done. Sometimes there are notes that end in Ref
underneath other nodes also ending in Ref, in those cases
it’s the top node that is turned into a <link> tag

Of course, there are exceptions and things to be aware of. Two of
these are illustrated in the above example. To correctly insert
the law reference (the SFS id ‘1960:644’) for tag to be produced
from the MultipleGenericRefs token ‘14 § 1 st. 6) och
6 §
‘, we have to plan ahead, when dealing with the parent
node (ExternalRefs). The formatter has built-in knowledge
of the special handling needed, and, when encountering a
ExternalRefs node, finds the ExternalLawRef node
child, stores the underlying LawRefID value, and later
picks this value up when formatting the tags for the two
GenericRef tokens.

To make this looping and recursing easier, I build a OO wrapper
around the array-based parse tree that mxTextTools return. This
was the subject of another
post
.

Note also that the ExternalLawRef token did not result in
a <link> tag, but the underlying LawRefID
token did. This was a consious decision (I thought it looked
better that way), and was implemented by creating a number of
extra subroutines in the formatter. Basically, the main function
acts as a generic dispatcher, by looping over all subtokens in a
tree, and for each token, checks if there’s a corresponding
format_tokenname() function. If so, call that,
otherwise call a generic formatter (which may, recursivly, make
use of the generic dispatcher). The code is pretty simple, but is
indicative of how neat stuff like this can be done in dynamic
langugages:

        try:
            formatter = getattr(self,"format_"+part.tag)
            res = formatter(part)
        except AttributeError:
            res = self.format_tokentree(part)
  

The other wierd thing is that ‘|’ sign in the term
varumärkes|lagen‘. This is swedish for ‘the trademark
law’, but since we like to write words together, this creates an
interesting challenge for creating the EBNF gramar. Basically, I
cannot find a way to match a word that ends in a specific suffix,
such as ‘lagen‘. The resulting parser is always ‘greedy’,
so there seem to be no way of matching these words without
matching all words. So, to fix this, I preprocess the text
before putting it through the parser, using normal python regular
expressions, which can be non-greedy, to put in that ‘|’
sign, which solves the problem. Then, after retrieving the string
from the tag formatter, I remove those signs.

One particular satisfying thing of the problem described in this
post is that how well it lends itselfs to automated regression
testing. Any new feature can easily be specified in a test case
before coding begins, and after it’s done, it’s easy to verify
that nothing that previously worked has been broken. More on
regression testing in a later post.

”EBNF Rocks!”, or undoing ten years of regex-inflicted damage

I’ve been parsing text with regexes for longer than as I’ve been
programming for a living. If there was some text extraction that
needed to be done, regexes was my first choice. Later on, I moved on
to HTML and XML parsers when I could, but there would often be some
sort of regexp magic operating on the text nodes.

But the problem of parsing swedish law texts, looking for internal
and external references, finally proved too tough for my beloved
regexp hammer. As an example, here is a sample paragraph: § 5 1982:713:

Bestämmelserna om livförsäkring, med undantag för 1 kap. 8 a §
samt 7 kap. 22, 23 och 26 §§, får tillämpas för skadeförsäkringar som
avses i 2 kap. 3 a § första stycket klasserna 1 och 2 samt för
avgångsbidragsförsäkringar.

(by the way, the linked HTML page is generated before I implemented
the EBNF based parsing described below. As you can see, there are quite a lot of places where my previous naive regex solution got it wrong.)

Quick primer on swedish and swedish law texts: ”1 kap.” means
Chapter 1, ”8 a §” means ”section 8 a”, ”första stycket” means ”first
paragraph” and the rest of the stuff is not really important. To
create the HTML pages I first create a XML document from the plaintext law, where I try to
find as much structure as possible. The most difficult part is finding
internal references. The end result I’m looking for is the
following:

Bestämmelserna om livförsäkring, med undantag för 
<ilink chapter="1" section="8 a">1 kap. 8 a §</ilink> samt 
<ilink chapter="7">7 kap.</ilink>
<ilink chapter="7" section="22">22</ilink>,
<ilink chapter="7" section="23">23</ilink> och
<ilink chapter="7" section="26">26 §§</ilink>, får
tillämpas för skadeförsäkringar som avses i
<ilink chapter="2" section="3 a" piece="1">2 kap. 3 a § första stycket</ilink>
klasserna 1 och 2 samt för avgångsbidragsförsäkringar.

This is a difficult problem to solve with rexes, partly because you
need to keep a lot of state while simultaneously iterating over an
unknown number of references (eg, when you reach ”26” and
create a <ilink> tag, you must remember that the
current chapter in this context is ”7”, and you must handle
the case when there isn’t a current chapter), partly because some
patterns are subpatterns of larger patterns (eg, there is a rule for
the simple case ”26 §”, but this matches a subset of the
larger case ”22, 23 och 26 §§”. Since there are so many rules
(and there are many more than I’ve shown in this simple example) a
solution that’s based on running several regexp transformations over
the same text quickly becomes unmanageble.

Well, after reading Chapter 4, ”Parsers and State-machines” from Text Processing in Python, I started
thinking about the problem from a more structured parsing view. I’ve
never really worked with EBNF parsers before. I could read a EBNF
grammar, but since I’ve never written a compiler or interpreter, it
didn’t really occur to me how useful they can be for other situations
as well.

The following is a grammar that can parse the above paragraph:

root               ::= (refs/ref/plain)+
refs               ::= (ChapterSectionRefs/SectionRefs)
ChapterSectionRefs ::= ChapterRef, wc, SectionRefs
ChapterRef         ::= ChapterRefID, c"kap."
ChapterRefID       ::= number, wc, (char, wc)?
SectionRefs        ::= (IntervalOrSingle,Comma,wc)*, IntervalOrSingle, wc, And, wc, LastSectionRefID, wc, DoubleSectionMark

IntervalOrSingle   ::= (IntervalSection/SingleSectionRefID)
SingleSectionRefID ::= number
FirstSectionRefID  ::= SingleSectionRefID
LastSectionRefID   ::= number
IntervalSection    ::= SingleSectionRefID, Hyphen, SingleSectionRefID

And                ::= 'och'
Or                 ::= 'eller'
Comma              ::= ','
Hyphen             ::= '-'
DoubleSectionMark  ::= '§§'

plain        ::= (wcs/word/number/punctuation)
wc           ::= [ \t\n\r\f\v]
wcs          ::= wc+
char         ::= [a-zA-ZåäöÅÄÖ]
word         ::= char+
digit        ::= [0-9]
number       ::= digit+
punctuation  ::= [][!@#$%^&()+=|\{}:;<>,.?/§"]

If you have basic knowledge of regexes, particularly bracket
expressions and repetition operators, the above grammar shouldn’t be
that difficult to understand. Just start at the top of the text to be
parsed, and try to satisfy the top rule (”root”), moving down
to the sub-rules (that’s probably not the correct technical term) as
you go. ‘(a/b/c)‘ means ”first try to satisfy a, if not successful try
b, if not successful try c” and ‘a, b, c‘ means ”satisfy a and then b
and then c”

The end result, when you feed this grammar and some law text into
SimpleParse, is a
result tree, which is a easily navigable data structure that I can use
to create the output text. For the example above, it will return a
plain‘ node, then a ‘refs‘ node, then another
plain‘ node, another ‘refs‘ and finally a last
plain‘ node. The ‘plain‘ nodes are everything that
the parser couldn’t match with the more specific rules (note that the
refs‘ and ‘ref‘ comes before ‘plain‘ in
the root rule), and I just print out them as-is.

For a ‘refs‘ node, I can dive into it’s subtree, where
I’ll find a single ‘ChapterSectionRefs‘ node, which in turn
will have three nodes: ‘ChapterRef‘, ‘wc‘,
SectionRefs‘. I’m sure you can see how this contiues.

Writing the code that takes this parse tree and constructs the XML
I want is not trivial, but compared to the regex mess I was in before,
it’s a walk in the park.

So, after ten years with my regex hammer, during which every text
parsing problem looked like a nail, I now have a EBNF
screwdriver. Better late than never!