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/10/09 12:22] georg.schmid Typo |
cc19:scallion [2019/10/09 12:26] georg.schmid Typos |
||
---|---|---|---|
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 === | ||