Training Exams for PL

Exam: Parsing RegExps

• Read carefully the pdf with the questions (opens in a new tab)
• Fill the code in this template repo ULL-ESIT-PL/exam-training-template (opens in a new tab)

AST Explorer (opens in a new tab) supports various regexp parsers. Feel free to play with them and have a look at the shapes of the ASTs.

Watch this video

and this other from minute 30:30:

Exam: Parsing JSON

• Exam Parsing JSON: pdf file. Question: Parse the JSON Language

Examples of Solutions

• Solution: JSON parser in nearley.js (opens in a new tab)
  • Task to do: Improve the solution by using your own lexical analyzer generator instead of the current moo lexer, removing the explicit use of white spaces (syntactic variable _ like in the production rule pair -> key _ ":" _ value) in the Nearley grammar
• Solution: JSON parser in yacc (opens in a new tab)
• Solution: JSON parser in pegjs (opens in a new tab)

Exam: Translator from Egg AST to AST Term

Question

Here is a variant of the previous exam.

Assume the input JSON contains an Egg AST and translate it to AST Term notation.

The Term Language to Summarize ASTs

Term is a DSL to summarize ASTs. Here is an attempt to describe the language:

term -> ('NAME' ':')? 'TYPE' '(' term (',' term)* ')'
  | leaf
leaf -> ('NAME' ':')? 'TYPE' ('{' 'ATTRIBUTE' '}')?

• Token 'NAME' is the name of the child in the node,
• Token 'TYPE' represents the type of the node,
• The token 'ATTRIBUTE' is the JSON stringify of a single attribute of the leaf node.

To summarize the AST the following rules are followed:

• Only the type of the node is shown
• Only one selected attribute of a leaf is shown (Between curly brackets)
• Array n-ary nodes are allowed (and they go between brackets)

Here is an example. Given the input program:

➜  evm2term git:(master) cat examples/property.egg 
x["sub", 1]("length") # 3

Whose JSON looks like:

➜  evm2term git:(master) cat examples/property.json
{
  "type": "apply",
  "operator": {
    "type": "property",
    "operator": {
      "type": "word",
      "line": 1,
      "col": 1,
      "length": 1,
      "name": "x"
    },
    "args": [
      {
        "type": "value",
        "value": "sub",
        "line": 1,
        "col": 3,
        "length": 5,
        "raw": "\"sub\""
      },
      {
        "type": "value",
        "value": 1,
        "line": 1,
        "col": 10,
        "length": 1
      }
    ]
  },
  "args": [
    {
      "type": "value",
      "value": "length",
      "line": 1,
      "col": 13,
      "length": 8,
      "raw": "\"length\""
    }
  ]
}

The output of the evm2term translator will be:

➜  evm2term git:(master) evm2term examples/property.json 
apply(op:property(op:word{x}, args:[value{sub},value{1}]), args:[value{length}])

Example of Solution

• See package evm2term (opens in a new tab) and file crguezl/evm2term/index.js (opens in a new tab) for a solution using estraverse