Labb 1

Parsing

Du kommer under labben skapa en parser och en runtime för ett enkelt språk. Språket implementerar en enkel variant av mönsterpassning, Se regexp.

Du ska skapa en grammatik som beskriver följande operatorer

• + eller, passar ett av två alternativ. Syntax: OP1+OP2
• * flera, passar ett eller flera upprepningar av en operand. Syntax: OP*
• () infångningsgrupp, deluttryck. Uttrycket parsas separat. Syntax: (EXPR)
• . tecken. matchar varlfritt tecken. Syntax: .
• {} räknare. matchar precis N stycken operander. Syntax: OP{3}
• \I ignorera versalisering. Syntax EXPR\I
• \O{} vilken infångningsgrupp som ska ges som output. Syntax: EXPR\O{2}. Default \O{0} hela matchningen.

OP beskriver en operand. Vad denna operand är bestämmer du själv i din grammatik.
EXPR beskriver ett giltigt uttryck, dvs en konstruktion som innehåller operander och operatorer enligt din grammatik.

Då programmet är klar och en matchning funnits ska programmet returnera EXIT_SUCCESS

Om ingen matchning kan göras ska programmet returnera EXIT__FAILURE och inte producera något output till stdout.

Exempel

Programkörning görs enklast så att man ger mönstret som argument och indata som input till stdin.

input.txt

Waterloo I was defeated, you won the war Waterloo promise to love you for ever more Waterloo couldn't escape if I wanted to Waterloo knowing my fate is to be with you Waterloo finally facing my Waterloo

>match "lo* could.{3}" < input.txt
loo couldn't
returkod EXIT_SUCCESS

>match ".*" < input.txt
Waterloo I was defeated, you won the war Waterloo promise to love you for ever more Waterloo couldn't escape if I wanted to Waterloo knowing my fate is to be with you Waterloo finally facing my Waterloo
returkod EXIT_SUCCESS

Valfritt:

>match "Waterloo (.*)the war\O{1}" < input.txt
I was defeated, you won returkod EXIT_SUCCESS

>match "promise to (Love+Hate) you\O{1}" < input.txt
``
returkod EXIT_FAILURE

>match "promise to (Love+Hate)\I you\O{1}" < input.txt
love
returkod EXIT_SUCCESS

Grammatik

Innan du påbörjar din implementation är det lämpligt att du författar en fullständig grammatik för operatorerna. Det är troligt att du behöver förändra/förbättra ditt första försök till grammatik.

Testa dina produktioner åtminstone på exemplena ovan.

Implementation

Det finns två realistiska sätt att implementera mönsterpassningen, det första blir mer kompakt men sannolikt mer komplicerat att implementera; det andra är utbyggbart men lite mer omfattande.

Direkt parsning

Implementera din grammatik som funktioner som parsar mönstret och direkt tillämpar operationerna på indatat.

Tillståndet i mönsterpassningen behöver då kunna gå tillbaka i mönsterpassningen om mönstret inte passar. Svårigheten består i få funktionerna att förstå i vilken kontext de utnyttjas.

Med parseträd

Först så skapar du ett parseträd som beskriver mönstret i grammatiska termer.

Din runtime tar parseträdet och går igenom hela indata och ser om det finns någon del av indatat som passar mönstret.

Parseträdet utnyttjar med fördel polymorfism, där en abstrakt bas kan vara utformad som

struct ASTNode{
  EvalResult virtual evaluate() = 0;
  std::vector<ASTNode*> operands;
};

Tips

Regex101.com kan vara upplysande.

Att lämna in

Redovisa i labbsal eller
Lämna in välkommenterad programkod och någorlunda uttömmande programkörningsexempel i en separat textfil.