La prestigieuse pizza de Paola

Analyse syntaxique

L'analyse syntaxique est le processus qui consiste à transformer du texte en données exploitables. Les fonctions du paquet String sont limitées à cet égard et les expressions régulières sont difficiles à utiliser, donc la façon idiomatique d'analyser en Elm est d'utiliser le paquet elm/parser.

Prenons un exemple : écrire un analyseur syntaxique pour (un sous-ensemble de) le langage de programmation LOLCODE. Considérons le programme commenté suivant :

HAI 1                 # program version 1
CAN HAS STDIO?        # import stdio
VISIBLE "HAI WORLD!"  # print "HAI WORLD!"
KTHXBYE               # end of program

Commençons par écrire un type Elm pour représenter les commandes possibles :

type Command
    = Version Int
    | Import String
    | Print String

Notre programme LOLCODE peut alors être modélisé comme une List Command. Écrivons maintenant un analyseur pour la ligne HAI 1 :

versionP : Parser Command
versionP =
    Parser.succeed Version
        |. Parser.keyword "HAI"
        |. Parser.spaces
        |= Parser.int

versionP est construit à l'aide d'un pipeline d'analyseurs. L'opérateur (|.) signifie « analyser la string mais jeter le résultat » et (|=) signifie « analyser la string et garder le résultat ». Dans cet exemple, Parser.keyword "HAI" va consommer un « HAI », mais ce résultat est ignoré. Parser.spaces va consommer un nombre quelconque de caractères ' ', '\n' et '\r', mais ce résultat sera lui aussi ignoré. Parser.int va analyser un entier, et la valeur de cet entier (disons 1) sera transmise au Parser.succeed Version situé en haut du pipeline, et l'analyseur parviendra à renvoyer la valeur Version 1.

Si l'un des analyseurs du pipeline échoue, il renvoie un Parser.DeadEnd et tout l'analyseur échoue. On peut exécuter un analyseur avec Parser.run :

Parser.run versionP "HAI 1"
    --> Ok (Version 1)
Parser.run versionP "HAI 2"
    --> Ok (Version 2)
Parser.run versionP "BYE 2"
    --> Err [{ problem = ExpectingKeyword "HAI", col = 1, row = 1 }]
Parser.run versionP "HAI MOM"
    --> Err [{ problem = ExpectingInt, col = 5, row = 1 }]

Attaquons maintenant la ligne « CAN HAS STDIO? » avec

importP : Parser Command
importP =
    Parser.succeed Import
        |. Parser.keyword "CAN HAS"
        |. Parser.spaces
        |= packageP
        |. Parser.symbol "?"

importP est lui aussi un pipeline d'analyseurs, mais cette fois il se termine par Parser.symbol, qui convient pour analyser des symboles comme « ? ». La valeur que l'on veut garder (le nom du paquet à importer) est analysée par

packageP : Parser String
packageP =
    Parser.chompWhile Char.isAlphaNum
        |> Parser.getChompedString
        |> Parser.map String.toLower

Comme on ne sait pas quel sera le nom du paquet, on ne peut pas utiliser Parser.keyword ; à la place, on utilise Parser.chompWhile, qui va consommer des caractères un par un tant qu'ils satisfont une condition (ici, être un caractère alphanumérique). Ces caractères consommés sont ensuite rassemblés par Parser.getChompedString, qui renvoie un Parser String. Ici, on souhaite normaliser les noms de paquets, donc on utilise Parser.map pour modifier la string contenue dans l'analyseur et la passer en minuscules.

Parser.run importP "CAN HAS STDIO?"
    --> Ok (Import "stdio")
Parser.run importP "CAN HAS StDiO?"
    --> Ok (Import "stdio")
Parser.run importP "CAN HAS STDIO"
    -->  Err [{ problem = ExpectingSymbol "?", col = 14, row = 1 }]

Ensuite, VISIBLE "HAI WORLD!" est analysé par

printP : Parser Command
printP =
    Parser.succeed Print
        |. Parser.keyword "VISIBLE"
        |. Parser.spaces
        |. Parser.symbol "\""
        |= stringP
        |. Parser.symbol "\""

stringP : Parser String
stringP =
    Parser.chompWhile (\c -> c /= '"')
        |> Parser.getChompedString

Parser.run printP "VISIBLE \"HAI WORLD!\""
    --> Ok (Print "HAI WORLD!")

On dispose maintenant d'un analyseur pour chaque commande. Bien sûr, dans un programme général, l'ordre de ces commandes ne peut pas être prédit, donc on construit un analyseur de commandes générique

commandP : Parser Command
commandP =
    Parser.oneOf
        [ versionP
        , importP
        , printP
        ]

Parser.oneOf essaie les analyseurs l'un après l'autre, dans l'ordre donné. Si un analyseur échoue, on essaie le suivant, mais s'il réussit, son résultat est renvoyé sans essayer les analyseurs restants. Si tous les analyseurs échouent, Parser.oneOf échoue.

Parser.run commandP "HAI 2"
    --> Ok (Version 2)
Parser.run commandP "CAN HAS STDIO?"
    --> Ok (Import "stdio")
Parser.run commandP "VISIBLE \"HAI WORLD!\""
    --> Ok (Print "HAI WORLD!")
Parser.run commandP "O NOES"
    --> Err [ { problem = ExpectingKeyword "HAI", col = 1, row = 1 }
    --      , { problem = ExpectingKeyword "CAN HAS", col = 1, row = 1 }
    --      , { problem = ExpectingKeyword "VISIBLE", col = 1, row = 1 }
    --      ]

Note que chaque tentative échouée produit un Parser.DeadEnd, que Parser.oneOf rassemble.

Pour analyser un programme complet, on doit analyser plusieurs commandes à la suite avec

programP : Parser (List Command)
programP =
    Parser.sequence
        { start = ""
        , separator = "\n"
        , end = "KTHXBYE"
        , spaces = Parser.succeed ()
        , item = commandP
        , trailing = Parser.Optional
        }

Parser.sequence est un analyseur très personnalisable, avec un certain nombre d'options. start, separator et end prennent des strings qui séparent les éléments de la séquence ; pour analyser une liste Elm, on utiliserait « [ », « , » et « ] ». spaces offre de la souplesse en prenant un analyseur qui gérera les espaces éventuels entre les éléments et les séparateurs ; pour analyser une liste Elm, on utiliserait Parser.spaces, mais ici on n'accepte aucun espace, donc on utilise Parser.succeed (), qui réussit immédiatement sans rien consommer. item prend l'analyseur d'élément et, enfin, trailing permet de décider si les séparateurs en fin de séquence sont Parser.Forbidden, Parser.Mandatory ou Parser.Optional.

Parser.run programP "HAI 2\nCAN HAS STDIO?\nKTHXBYE"
    --> Ok [Version 2, Import "stdio"]
Parser.run programP "KTHXBYE"
    --> Ok []
Parser.run programP "HAI 2\nCAN HAS STDIO?\n"
    --> Err [ { problem = ExpectingKeyword "HAI", col = 1, row = 3 }
    --      , { problem = ExpectingKeyword "CAN HAS", col = 1, row = 3 }
    --      , { problem = ExpectingKeyword "VISIBLE", col = 1, row = 3 }
    --      , { problem = Expecting "KTHXBYE", col = 1, row = 3 }
    --      ]

Quand un analyseur réussit, il arrête de consommer la string

Parser.run Parser.int "1"
    --> Ok 1
Parser.run Parser.int "1 BTW VISIBLE \"U SEE NOTHING\""
    --> Ok 1

Donc, si l'on veut s'assurer que l'on a bien tout analysé dans la string, on peut utiliser Parser.end

fullProgramP : Parser (List Command)
fullProgramP =
    programP
        |. Parser.spaces
        |. Parser.end

Parser.run fullProgramP "HAI 2\nCAN HAS STDIO?\nKTHXBYE"
    --> Ok [Version 2, Import "stdio"]
Parser.run fullProgramP "HAI 2\nCAN HAS STDIO?\nKTHXBYE\nBTW VISIBLE \"U SEE NOTHING\""
    --> Err [{ problem = ExpectingEnd, col = 1, row = 4 }]

Enfin, il arrive parfois qu'on doive faire échouer un analyseur en fonction de son contenu analysé. Par exemple, si l'on avait besoin d'un analyseur qui fait échouer les programmes commençant par deux commandes « HAI » d'affilée, on pourrait utiliser

singleVersionProgramP : Parser (List Command)
singleVersionProgramP =
    fullProgramP
        |> Parser.andThen
            (\commands ->
                case commands of
                    (Version _) :: (Version _) :: _ ->
                        Parser.problem "Multiple versions defined"

                    _ ->
                        Parser.succeed commands
            )

Parser.andThen peut inspecter le contenu d'un analyseur et renvoie un nouvel analyseur en fonction de sa valeur. Ici, on fait échouer l'analyseur avec un message personnalisé grâce à Parser.problem dans un cas, et on renvoie la valeur d'origine dans l'autre.

Parser.run singleVersionProgramP "HAI 2\nCAN HAS STDIO?\nKTHXBYE"
    --> Ok [Version 2, Import "stdio"]
Parser.run singleVersionProgramP "HAI 1\nHAI 2\nCAN HAS STDIO?\nKTHXBYE"
    --> Err [{ problem = Problem "Multiple versions defined", col = 8, row = 4 }]