Module Tools.YYgen

This program creates a parser from the result of running byacc -v on a yacc grammar. It reads the resulting files "y.tab.c" and "y.output" in the current directory and uses the information therein to construct a frege program.

Each grammar rule is associated with a reduction function of type

  item1 -> ... -> item2 -> result

where the item types are either tokens (provided as input to the parser) or results of other grammar rules. All rules of a nonterminal grammar symbol will have the same result type. Example:

 %{
 package Calculator
 numberFrom :: Token -> Double
 %}

 %token NUMBER PI
 %start sum
 %%
 sum : product '+' product { \a\_\b -> a + b }  // was: $$ = $1 + $3
       | product                                // was: $$ = $1
       ;
 product: term '*' term { \a\b\c -> a * b }
       | term
       ;
 term: NUMBER              { numberFrom }
       | PI                { const 3.14159 }
       | '-' term          { \_\b -> negate b }
       | '(' sum ')'       { \_\b\_ -> b }
       ;
 %%
 data TokenID = NUMBER | PI | OPERATOR
 derive Show TokenID
 derive Ord TokenID
 data Token = N Double | Pi | Op Char
 derive Show Token
 yyshowToken = Token.show
 yyniceToken (N d) = show d
 yyniceToken Pi = "pi"
 yyniceToken (Op c) = show c
 yytoken :: Token -> TokenID
 yytoken (N _) = NUMBER
 yytoken Pi    = PI
 yytoken Op    = OPERATOR

 yychar :: Token -> Char
 yychar (Op c) = c
 yychar _ = const 'ยง'  // paragraph symbol not used elsewhere

 yyfromId NUMBER = N 42.0
 yyfromId PI     = PI
 // yyfromId OPERATOR = not needed, as the parser knows nothing of OPERATOR

 yyfromCh :: Char -> Token
 yyfromCh c = Op c

 yyline = const 0      // no way to know in this example

So far, this is just a good old yacc grammar, except that the semantic actions are frege expressions, and the code before an after the "%%" markers is frege code.

Each semantic action is expected to be a function that takes as many arguments as there are items in its rule. Hence, in the first rule of nonterminal "sum" the left product will be bound to /a/, the "+" token is ignored and the right product to /b/. A missing action is equivalent to the identity function, therefore in the second rule of nonterminal "sum", the sum will be just the product.

The parser generated from this will have a function

 yyparse :: [Token] -> Maybe Double

since Double is the result type of the rules associated with the start symbol and tokens are obviously of type Token (due to application of user supplied function numberFrom). The result will be Maybe.Nothing if the parser could not reduce the start symbol (i.e., when there were nonrecoverable syntax errors) and (Maybe.Just x) otherwise, where /x/ is the result of one of the semantic actions associated with the "%start" symbol.

The parser itself does not make any assumptions about what a token is. Instead, it relies on the following user supplied functions:

 yytoken  :: token -> tid
 yyfromId :: tid -> token

where /token/ is the type of tokens and /tid/ is the type of the token constants defined in the "%token" directive. The /yytoken/ function must be total, i.e. all possible token values must produce some token constant, yet this does not have to be one of the constants that is listed in the "%token" directive.

The /yyfromId/ function must produce an example token value for each token constant the parser knows of through the "%token" directive. Both functions have to be there only when a "%token" directive is present.

If the grammar uses character constants, the following functions must be present:

 yychar :: token -> Char
 yyfromCh :: Char -> token

The /yychar/ function must be total, all possible token values must be mapped to some character. Use a character value that is not used in the grammar for tokens that have no representation as a character value.

The /yyfromCh/ function maps back characters to token values. The /yyfrom../ functions are used in error recovery to supply tokens that are expected, but missing.

Here is an example of how the parser may determine what to do in state 42:

 yyaction 42 tok = case yychar tok of
       '*'   -> Shift 57
       _ -> case yytoken tok of
           NUMBER -> Shift 96
           _      -> Reduce 5

In addition, the parser needs the following functions:

 yynice :: token -> String
 yyshow :: token -> String
 yyline :: token -> Show:a
 yyerror :: Show:a -> String -> c

/yynice/ is used by the parser to construct error messages like this

 "syntax error, expected ',', found " ++ yynice errortoken
 "syntax error, expected IDENTIFIER, found " ++ yynice errortoken
 "syntax error on " ++ yynice errortoken

/yyshow/ is used in trace output and is intended for a most detailed display of tokens as they are recognized by the parser.

/yyline/ is used to extract line number information from a token, it is thus a good idea to design the lexical analyzer so that a token is able to tell where it was found.

/yyerror/ is used to emit messages about syntax errors. The first argument will be either the string "EOF" or the result of applying /yyline/ to a token. The second argument is a string that describes the error. The result of yyerror is evaluated, but ignored.

Imports

Table of Content

Definitions

resource โˆท Maybe ๐–† โ†’ String
yygenpar โˆท Maybe a โ†’ IO [String]
loadResource โˆท Maybe a โ†’ MutableIO URLClassLoader โ†’ IO [String]
loadUrl โˆท URL โ†’ IO [String]
uncr โˆท String โ†’ String

remove carriage returns from strings -

fileContent โˆท String โ†’ IO [String]

give back file content as list of lines -

scanlines โˆท [String] โ†’ ([String], [(Int, [String])])
scanytablines โˆท [String] โ†’ ([String], [String], [(Int, String)], [(String, String)], TreeMap String String)
compiletypes โˆท TreeMap String String โ†’ [String] โ†’ String
genshowsi โˆท [String] โ†’ String
data Item

Constructors

Acc
Def
End
Lit (String)
NT (String)
T (String)
data Prod

Constructors

Prod Int   Item   [Item]
data Todo

Constructors

Accept
Error
Goto
Reduce
Shift
data Action

Constructors

A Todo   Item   Int
data YYState

Constructors

St Int   [Prod]   [Action]   [Action]
mkState โˆท (Int, [String]) โ†’ YYState
genitems โˆท [Item] โ†’ [String]
genitem โˆท Int โ†’ Item โ†’ String
niceitem โˆท Item โ†’ String
genst โˆท YYState โ†’ String
printstates โˆท [YYState] โ†’ MutableIO PrintWriter โ†’ IO ()
extrrule โˆท YYState โ†’ [Prod]
extrrules โˆท [YYState] โ†’ [Prod]
printpr โˆท Maybe ๐–† โ†’ [YYState] โ†’ [(Int, String)] โ†’ MutableIO PrintWriter โ†’ IO ()
genacc โˆท Show ๐–† โ‡’ ๐–† โ†’ Prod โ†’ String
genrule โˆท Prod โ†’ String
genprod โˆท Maybe ๐–† โ†’ Prod โ†’ [(Int, String)] โ†’ String
genstate โˆท Show ๐–† โ‡’ ๐–† โ†’ [Prod] โ†’ Action โ†’ String
gengoto1 โˆท ๐–† โ†’ Action โ†’ [Prod] โ†’ [(๐–†, Int, Int)]
gengotos1 โˆท [Prod] โ†’ YYState โ†’ [(Int, Int, Int)]
gengoto2 โˆท Action โ†’ [Prod] โ†’ [(Int, Int)] โ†’ [(Int, Int)]
gengotos2 โˆท [Prod] โ†’ YYState โ†’ (Int, [(Int, Int)])
sortfst โˆท Ord ๐–ˆ โ‡’ (๐–ˆ, ๐–†) โ†’ (๐–ˆ, ๐–‡) โ†’ Bool
sortgos โˆท (Ord ๐–‰, Ord ๐–ˆ) โ‡’ (๐–‰, ๐–†, ๐–ˆ) โ†’ (๐–‰, ๐–‡, ๐–ˆ) โ†’ Ordering
altgotos โˆท [Prod] โ†’ [YYState] โ†’ [(Int, Int, Int)] โ†’ [(Int, Int, Int)]
altgotos2 โˆท [Prod] โ†’ [YYState] โ†’ [(Int, [(Int, Int)])]
listmax โˆท Int
pracase โˆท Show a โ‡’ String โ†’ [(Int, a)] โ†’ MutableIO PrintWriter โ†’ IO ()
collecteactions โˆท YYState โ†’ Bool
collectacceptactions โˆท YYState โ†’ Bool
actions โˆท [YYState] โ†’ [(Int, String)]
recoveries โˆท TreeMap String String โ†’ [YYState] โ†’ [(Int, String)]
eactions โˆท [YYState] โ†’ [(Int, String)]
numbertypes โˆท Ord ๐–† โ‡’ Int โ†’ [๐–†] โ†’ TreeMap ๐–† Int โ†’ TreeMap ๐–† Int
numprod โˆท Prod โ†’ (Int, String)
listred โˆท Show ๐–† โ‡’ (๐–†, String) โ†’ String
printreds โˆท Show ๐–† โ‡’ [(๐–†, String)] โ†’ MutableIO PrintWriter โ†’ IO ()
gengos โˆท (Ord ๐–†, ListSource ๐–‡, Show ๐–ˆ, Show ๐–‰, Show ๐–†, Ord ๐–‰, Ord ๐–ˆ) โ‡’ ๐–‡ (๐–†, ๐–‰, ๐–ˆ) โ†’ String
printgos โˆท [(Int, [(Int, Int)])] โ†’ MutableIO PrintWriter โ†’ IO ()

create frege code for go tabs

format1 โˆท String โ†’ Int โ†’ String
pure native java.lang.String.format
main โˆท [String] โ†’ IO ()
cantwrite โˆท String โ†’ FileNotFoundException โ†’ IO ()
mainIO โˆท Maybe String โ†’ String โ†’ IO ()

Instances

instance Eq Item

Member Functions

!= โˆท Item โ†’ Item โ†’ Bool
infix  7

inherited from Eq.!=

== โˆท Item โ†’ Item โ†’ Bool
infix  7

Function generated for derived instance.

hashCode โˆท Item โ†’ Int

Function generated for derived instance.

instance Eq Prod

Member Functions

!= โˆท Prod โ†’ Prod โ†’ Bool
infix  7

inherited from Eq.!=

== โˆท Prod โ†’ Prod โ†’ Bool
infix  7

Function generated for derived instance.

hashCode โˆท Prod โ†’ Int

Function generated for derived instance.

instance Ord Item

Member Functions

< โˆท Item โ†’ Item โ†’ Bool
infix  9

inherited from Ord.<

<= โˆท Item โ†’ Item โ†’ Bool
infix  9

inherited from Ord.<=

<=> โˆท Item โ†’ Item โ†’ Ordering
infix  8

Function generated for derived instance.

> โˆท Item โ†’ Item โ†’ Bool
infix  9

inherited from Ord.>

>= โˆท Item โ†’ Item โ†’ Bool
infix  9

inherited from Ord.>=

compare โˆท Item โ†’ Item โ†’ Ordering
infix  8

inherited from Ord.compare

max โˆท Item โ†’ Item โ†’ Item

inherited from Ord.max

min โˆท Item โ†’ Item โ†’ Item

inherited from Ord.min

instance Ord Prod

Member Functions

< โˆท Prod โ†’ Prod โ†’ Bool
infix  9

inherited from Ord.<

<= โˆท Prod โ†’ Prod โ†’ Bool
infix  9

inherited from Ord.<=

<=> โˆท Prod โ†’ Prod โ†’ Ordering
infix  8
> โˆท Prod โ†’ Prod โ†’ Bool
infix  9

inherited from Ord.>

>= โˆท Prod โ†’ Prod โ†’ Bool
infix  9

inherited from Ord.>=

compare โˆท Prod โ†’ Prod โ†’ Ordering
infix  8

inherited from Ord.compare

max โˆท Prod โ†’ Prod โ†’ Prod

inherited from Ord.max

min โˆท Prod โ†’ Prod โ†’ Prod

inherited from Ord.min

instance Show Action

Member Functions

display โˆท Action โ†’ String

inherited from Show.display

show โˆท Action โ†’ String

Function generated for derived instance.

showChars โˆท Action โ†’ [Char]

inherited from Show.showChars

showList โˆท [Action] โ†’ String โ†’ String

inherited from Show.showList

showsPrec โˆท Int โ†’ Action โ†’ String โ†’ String

inherited from Show.showsPrec

showsub โˆท Action โ†’ String

Function generated for derived instance.

instance Show Item

Member Functions

display โˆท Item โ†’ String

inherited from Show.display

show โˆท Item โ†’ String

Function generated for derived instance.

showChars โˆท Item โ†’ [Char]

inherited from Show.showChars

showList โˆท [Item] โ†’ String โ†’ String

inherited from Show.showList

showsPrec โˆท Int โ†’ Item โ†’ String โ†’ String

inherited from Show.showsPrec

showsub โˆท Item โ†’ String

Function generated for derived instance.

instance Show Prod

Member Functions

display โˆท Prod โ†’ String

inherited from Show.display

show โˆท Prod โ†’ String

Function generated for derived instance.

showChars โˆท Prod โ†’ [Char]

inherited from Show.showChars

showList โˆท [Prod] โ†’ String โ†’ String

inherited from Show.showList

showsPrec โˆท Int โ†’ Prod โ†’ String โ†’ String

inherited from Show.showsPrec

showsub โˆท Prod โ†’ String

Function generated for derived instance.

instance Show Todo

Member Functions

display โˆท Todo โ†’ String

inherited from Show.display

show โˆท Todo โ†’ String

Function generated for derived instance.

showChars โˆท Todo โ†’ [Char]

inherited from Show.showChars

showList โˆท [Todo] โ†’ String โ†’ String

inherited from Show.showList

showsPrec โˆท Int โ†’ Todo โ†’ String โ†’ String

inherited from Show.showsPrec

showsub โˆท Todo โ†’ String

Function generated for derived instance.

instance Show YYState

Member Functions

display โˆท YYState โ†’ String

inherited from Show.display

show โˆท YYState โ†’ String

Function generated for derived instance.

showChars โˆท YYState โ†’ [Char]

inherited from Show.showChars

showList โˆท [YYState] โ†’ String โ†’ String

inherited from Show.showList

showsPrec โˆท Int โ†’ YYState โ†’ String โ†’ String

inherited from Show.showsPrec

showsub โˆท YYState โ†’ String

Function generated for derived instance.

Functions and Values by Type

TreeMap String String โ†’ [String] โ†’ String

compiletypes

TreeMap String String โ†’ [YYState] โ†’ [(Int, String)]

recoveries

(Int, [String]) โ†’ YYState

mkState

Maybe String โ†’ String โ†’ IO ()

mainIO

String โ†’ FileNotFoundException โ†’ IO ()

cantwrite

String โ†’ Int โ†’ String

format1

String โ†’ IO [String]

fileContent

String โ†’ String

uncr

String โ†’ Item

Item.NT, Item.Lit, Item.T

[(Int, [(Int, Int)])] โ†’ MutableIO PrintWriter โ†’ IO ()

printgos

[String] โ†’ ([String], [String], [(Int, String)], [(String, String)], TreeMap String String)

scanytablines

[String] โ†’ ([String], [(Int, [String])])

scanlines

[String] โ†’ IO ()

main

[String] โ†’ String

genshowsi

[Action] โ†’ String โ†’ String

Show_Action.showList

[Item] โ†’ String โ†’ String

Show_Item.showList

[Item] โ†’ [String]

genitems

[Prod] โ†’ String โ†’ String

Show_Prod.showList

[Prod] โ†’ [YYState] โ†’ [(Int, Int, Int)] โ†’ [(Int, Int, Int)]

altgotos

[Prod] โ†’ [YYState] โ†’ [(Int, [(Int, Int)])]

altgotos2

[Prod] โ†’ YYState โ†’ (Int, [(Int, Int)])

gengotos2

[Prod] โ†’ YYState โ†’ [(Int, Int, Int)]

gengotos1

[Todo] โ†’ String โ†’ String

Show_Todo.showList

[YYState] โ†’ MutableIO PrintWriter โ†’ IO ()

printstates

[YYState] โ†’ String โ†’ String

Show_YYState.showList

[YYState] โ†’ [(Int, String)]

actions, eactions

[YYState] โ†’ [Prod]

extrrules

URL โ†’ IO [String]

loadUrl

Int โ†’ [Prod] โ†’ [Action] โ†’ [Action] โ†’ YYState

YYState.St

Int โ†’ Action โ†’ String โ†’ String

Show_Action.showsPrec

Int โ†’ Item โ†’ String โ†’ String

Show_Item.showsPrec

Int โ†’ Item โ†’ [Item] โ†’ Prod

Prod.Prod

Int โ†’ Item โ†’ String

genitem

Int โ†’ Prod โ†’ String โ†’ String

Show_Prod.showsPrec

Int โ†’ Todo โ†’ String โ†’ String

Show_Todo.showsPrec

Int โ†’ YYState โ†’ String โ†’ String

Show_YYState.showsPrec

Action โ†’ [Prod] โ†’ [(Int, Int)] โ†’ [(Int, Int)]

gengoto2

Action โ†’ String

Show_Action.showsub, Show_Action.display, Show_Action.show

Action โ†’ [Char]

Show_Action.showChars

Item โ†’ Item โ†’ Bool

Eq_Item.!=, Eq_Item.==, Ord_Item.>=, Ord_Item.<, Ord_Item.<=, Ord_Item.>

Item โ†’ Item โ†’ Ordering

Ord_Item.compare, Ord_Item.<=>

Item โ†’ Item โ†’ Item

Ord_Item.min, Ord_Item.max

Item โ†’ String

niceitem, Show_Item.showsub, Show_Item.display, Show_Item.show

Item โ†’ [Char]

Show_Item.showChars

Item โ†’ Int

Eq_Item.hashCode

Prod โ†’ Prod โ†’ Bool

Eq_Prod.!=, Eq_Prod.==, Ord_Prod.>=, Ord_Prod.<, Ord_Prod.<=, Ord_Prod.>

Prod โ†’ Prod โ†’ Ordering

Ord_Prod.compare, Ord_Prod.<=>

Prod โ†’ Prod โ†’ Prod

Ord_Prod.min, Ord_Prod.max

Prod โ†’ (Int, String)

numprod

Prod โ†’ String

genrule, Show_Prod.showsub, Show_Prod.display, Show_Prod.show

Prod โ†’ [Char]

Show_Prod.showChars

Prod โ†’ Int

Eq_Prod.hashCode

Todo โ†’ Item โ†’ Int โ†’ Action

Action.A

Todo โ†’ String

Show_Todo.showsub, Show_Todo.display, Show_Todo.show

Todo โ†’ [Char]

Show_Todo.showChars

YYState โ†’ String

genst, Show_YYState.showsub, Show_YYState.display, Show_YYState.show

YYState โ†’ [Char]

Show_YYState.showChars

YYState โ†’ [Prod]

extrrule

YYState โ†’ Bool

collectacceptactions, collecteactions

Int

listmax

Item

Item.End, Item.Acc, Item.Def

Todo

Todo.Reduce, Todo.Error, Todo.Accept, Todo.Goto, Todo.Shift

Maybe a โ†’ MutableIO URLClassLoader โ†’ IO [String]

loadResource

Maybe a โ†’ IO [String]

yygenpar

Maybe ๐–† โ†’ [YYState] โ†’ [(Int, String)] โ†’ MutableIO PrintWriter โ†’ IO ()

printpr

Maybe ๐–† โ†’ Prod โ†’ [(Int, String)] โ†’ String

genprod

Maybe ๐–† โ†’ String

resource

๐–† โ†’ Action โ†’ [Prod] โ†’ [(๐–†, Int, Int)]

gengoto1

Ord ๐–† โ‡’ Int โ†’ [๐–†] โ†’ TreeMap ๐–† Int โ†’ TreeMap ๐–† Int

numbertypes

Show a โ‡’ String โ†’ [(Int, a)] โ†’ MutableIO PrintWriter โ†’ IO ()

pracase

Show ๐–† โ‡’ (๐–†, String) โ†’ String

listred

Show ๐–† โ‡’ [(๐–†, String)] โ†’ MutableIO PrintWriter โ†’ IO ()

printreds

Show ๐–† โ‡’ ๐–† โ†’ [Prod] โ†’ Action โ†’ String

genstate

Show ๐–† โ‡’ ๐–† โ†’ Prod โ†’ String

genacc

Ord ๐–ˆ โ‡’ (๐–ˆ, ๐–†) โ†’ (๐–ˆ, ๐–‡) โ†’ Bool

sortfst

(Ord ๐–†, ListSource ๐–‡, Show ๐–ˆ, Show ๐–‰, Show ๐–†, Ord ๐–‰, Ord ๐–ˆ) โ‡’ ๐–‡ (๐–†, ๐–‰, ๐–ˆ) โ†’ String

gengos

(Ord ๐–‰, Ord ๐–ˆ) โ‡’ (๐–‰, ๐–†, ๐–ˆ) โ†’ (๐–‰, ๐–‡, ๐–ˆ) โ†’ Ordering

sortgos

Valid HTML 4.01 Strict