Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
cc19:scallion [2019/07/25 10:05] romain |
cc19:scallion [2019/10/09 12:26] georg.schmid Typos |
||
---|---|---|---|
Line 9: | Line 9: | ||
* Writing the parser in a //domain specific language// (DSL) and using a parser generator (such as Bison) to produce the parser. | * Writing the parser in a //domain specific language// (DSL) and using a parser generator (such as Bison) to produce the parser. | ||
- | An other approach, which we will be using, is //parser combinators//. The idea behind the approach is very simple: | + | Another approach, which we will be using, is //parser combinators//. The idea behind the approach is very simple: |
* Have a set of simple primitive parsers, and | * Have a set of simple primitive parsers, and | ||
* Have ways to combine them together into more and more complex parsers. Hence the name //parser combinators//. | * Have ways to combine them together into more and more complex parsers. Hence the name //parser combinators//. | ||
- | Usually, those primitive parsers and combinators are provided as a library directly in the language used by the compiler. In our case, we will be working with **Scallion**, a Scala parser combinators library developped by //LARA//. | + | Usually, those primitive parsers and combinators are provided as a library directly in the language used by the compiler. In our case, we will be working with **Scallion**, a Scala parser combinators library developed by //LARA//. |
Parser combinators have many advantages – the main one being easy to write, read and maintain. | Parser combinators have many advantages – the main one being easy to write, read and maintain. | ||
Line 26: | Line 26: | ||
==== Setup ==== | ==== Setup ==== | ||
- | In Scallion, parsers are called defined within a trait called ''%%Syntaxes%%''. This trait takes as parameters two types: | + | In Scallion, parsers are defined within a trait called ''%%Syntaxes%%''. This trait takes as parameters two types: |
* The type of tokens, | * The type of tokens, | ||
Line 47: | Line 47: | ||
==== Writing Parsers ==== | ==== Writing Parsers ==== | ||
- | When writing a parser using parser combinators, one defines many smaller parsers and combine them together into more and more complex parsers. The top-level, most complex, of those parser then defines the entire syntax for the language. In our case, that top-level parser will be called ''%%program%%''. | + | When writing a parser using parser combinators, one defines many smaller parsers and combines them together into more and more complex parsers. The top-level, most complex, of those parser then defines the entire syntax for the language. In our case, that top-level parser will be called ''%%program%%''. |
All those parsers are objects of the type ''%%Syntax[A]%%''. The type parameter ''%%A%%'' indicates the type of values produced by the parser. For instance, a parser of type ''%%Syntax[Int]%%'' produces ''%%Int%%''s and a parser of type ''%%Syntax[Expr]%%'' produces ''%%Expr%%''s. Our top-level parser has the following signature: | All those parsers are objects of the type ''%%Syntax[A]%%''. The type parameter ''%%A%%'' indicates the type of values produced by the parser. For instance, a parser of type ''%%Syntax[Int]%%'' produces ''%%Int%%''s and a parser of type ''%%Syntax[Expr]%%'' produces ''%%Expr%%''s. Our top-level parser has the following signature: | ||
Line 54: | Line 54: | ||
lazy val program: Parser[Program] = ... | lazy val program: Parser[Program] = ... | ||
</code> | </code> | ||
- | Contrarily to the types of tokens and token kinds, which are fixed, the type of value produced is a type parameter of the various ''%%Syntax%%''s. This allows your different parsers to produce different type of values. | + | Contrary to the types of tokens and token kinds, which are fixed, the type of values produced is a type parameter of the various ''%%Syntax%%''s. This allows your different parsers to produce different types of values. |
The various parsers are stored as ''%%val%%'' members of the ''%%Parser%%'' object. In the case of mutually dependent parsers, we use ''%%lazy val%%'' instead. | The various parsers are stored as ''%%val%%'' members of the ''%%Parser%%'' object. In the case of mutually dependent parsers, we use ''%%lazy val%%'' instead. | ||
Line 91: | Line 91: | ||
==== Parsers and Grammars ==== | ==== Parsers and Grammars ==== | ||
- | As you will see, parsers built using parser combinators will look a lot like grammars. However, contrarily to grammars, parsers not only describe the syntax or your language, but also directly specify how to turn this syntax into a value. Also, as we will see, parser combinators have a richer vocabulary than your usual //BNF// grammars. | + | As you will see, parsers built using parser combinators will look a lot like grammars. However, unlike grammars, parsers not only describe the syntax of your language, but also directly specify how to turn this syntax into a value. Also, as we will see, parser combinators have a richer vocabulary than your usual //BNF// grammars. |
Interestingly, a lot of concepts that you have seen on grammars, such as ''%%FIRST%%'' sets and nullability can be straightforwardly transposed to parsers. | Interestingly, a lot of concepts that you have seen on grammars, such as ''%%FIRST%%'' sets and nullability can be straightforwardly transposed to parsers. | ||
Line 102: | Line 102: | ||
definition.first === Set(def, abstract, case) | definition.first === Set(def, abstract, case) | ||
</code> | </code> | ||
+ | |||
=== Nullability === | === Nullability === | ||