Compiled: Wed Dec 05 00:09:07 PST 2012 from source file: frege/tools/YYgen.fr
Package Documentation
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" diretive. 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.
Table of Content
Imports
-
instance Eq Item
-
Member Functions
-
!= :: Item -> Item -> Bool
-
inherited from Eq.!=
-
/= :: Item -> Item -> Bool
-
inherited from Eq./=
-
== :: Item -> Item -> Bool
-
Function generated for derived istance.
-
hashCode :: Item -> Int
-
Function generated for derived istance.
-
instance Eq Prod
-
Member Functions
-
!= :: Prod -> Prod -> Bool
-
inherited from Eq.!=
-
/= :: Prod -> Prod -> Bool
-
inherited from Eq./=
-
== :: Prod -> Prod -> Bool
-
Function generated for derived istance.
-
hashCode :: Prod -> Int
-
Function generated for derived istance.
-
instance Ord Item
-
Member Functions
-
< :: Item -> Item -> Bool
-
inherited from Ord.<
-
<= :: Item -> Item -> Bool
-
inherited from Ord.<=
-
<=> :: Item -> Item -> Ordering
-
Function generated for derived istance.
-
> :: Item -> Item -> Bool
-
inherited from Ord.>
-
>= :: Item -> Item -> Bool
-
inherited from Ord.>=
-
compare :: Item -> Item -> Ordering
-
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
-
inherited from Ord.<
-
<= :: Prod -> Prod -> Bool
-
inherited from Ord.<=
-
<=> :: Prod -> Prod -> Ordering
-
-
> :: Prod -> Prod -> Bool
-
inherited from Ord.>
-
>= :: Prod -> Prod -> Bool
-
inherited from Ord.>=
-
compare :: Prod -> Prod -> Ordering
-
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 istance.
-
showList :: [Action] -> String -> String
-
inherited from Show.showList
-
showsPrec :: Int -> Action -> String -> String
-
inherited from Show.showsPrec
-
showsub :: Action -> String
-
Function generated for derived istance.
-
instance Show Item
-
Member Functions
-
display :: Item -> String
-
inherited from Show.display
-
show :: Item -> String
-
Function generated for derived istance.
-
showList :: [Item] -> String -> String
-
inherited from Show.showList
-
showsPrec :: Int -> Item -> String -> String
-
inherited from Show.showsPrec
-
showsub :: Item -> String
-
Function generated for derived istance.
-
instance Show Prod
-
Member Functions
-
display :: Prod -> String
-
inherited from Show.display
-
show :: Prod -> String
-
Function generated for derived istance.
-
showList :: [Prod] -> String -> String
-
inherited from Show.showList
-
showsPrec :: Int -> Prod -> String -> String
-
inherited from Show.showsPrec
-
showsub :: Prod -> String
-
Function generated for derived istance.
-
instance Show Todo
-
Member Functions
-
display :: Todo -> String
-
inherited from Show.display
-
show :: Todo -> String
-
Function generated for derived istance.
-
showList :: [Todo] -> String -> String
-
inherited from Show.showList
-
showsPrec :: Int -> Todo -> String -> String
-
inherited from Show.showsPrec
-
showsub :: Todo -> String
-
Function generated for derived istance.
-
instance Show YYState
-
Member Functions
-
display :: YYState -> String
-
inherited from Show.display
-
show :: YYState -> String
-
Function generated for derived istance.
-
showList :: [YYState] -> String -> String
-
inherited from Show.showList
-
showsPrec :: Int -> YYState -> String -> String
-
inherited from Show.showsPrec
-
showsub :: YYState -> String
-
Function generated for derived istance.
-
data Action
-
Constructors
-
A Todo Item Int
-
-
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 YYState
-
Constructors
-
St Int [Prod] [Action] [Action]
-
-
actions :: [YYState] -> ListKV Int String
-
-
altgotos :: [Prod] -> [YYState] -> [(Int, Int, Int)] -> [(Int, Int, Int)]
-
-
altgotos2 :: [Prod] -> [YYState] -> ListKV Int (ListKV Int Int)
-
-
append :: ListLike α => α β -> α β -> α β
-
-
brFromIS :: String -> InputStream -> IO (Exception BufferedReader)
-
-
brFromISR :: Either α InputStreamReader -> IO (Either α BufferedReader)
-
-
collectacceptactions :: YYState -> Bool
-
-
collecteactions :: YYState -> Bool
-
-
compiletypes :: Tree String String -> [String] -> String
-
-
eactions :: [YYState] -> ListKV Int String
-
-
extrrule :: YYState -> [Prod]
-
-
extrrules :: [YYState] -> [Prod]
-
-
fileContent :: String -> IO [String]
-
give back file content as list of lines
-
fio :: Monad m => (r->m r) -> (a->r->m r) -> [a] -> r -> m r
-
-
genacc :: Show α => α -> Prod -> String
-
-
gengos :: (Show γ, Show α, Show δ, Ord α, Ord δ, Ord γ, ListSource β) => β (γ, α, δ) -> String
-
-
gengoto1 :: α -> Action -> [Prod] -> [(α, Int, Int)]
-
-
gengoto2 :: Action -> [Prod] -> ListKV Int Int -> ListKV Int Int
-
-
gengotos1 :: [Prod] -> YYState -> [(Int, Int, Int)]
-
-
gengotos2 :: [Prod] -> YYState -> (Int, ListKV Int Int)
-
-
genitem :: Int -> Item -> String
-
-
genitems :: [Item] -> [String]
-
-
genprod :: Maybe α -> Prod -> ListKV Int String -> String
-
-
genrule :: Prod -> String
-
-
genshowsi :: [String] -> String
-
-
genst :: YYState -> String
-
-
genstate :: Show α => α -> [Prod] -> Action -> String
-
-
grep :: (α->Bool) -> [α] -> [α]
-
-
listmax :: Int
-
-
listred :: Show α => (α, String) -> String
-
-
loadInputStream :: InputStream -> IO [String]
-
-
loadRessource :: Maybe a -> URLClassLoader -> IO [String]
-
-
loadUrl :: URL -> IO [String]
-
-
main :: [String] -> IO ()
-
-
mainIO :: Show α => Maybe α -> String -> IO ()
-
-
mkState :: (Int, [String]) -> YYState
-
-
niceitem :: Item -> String
-
-
numbertypes :: Ord α => Int -> [α] -> Tree α Int -> Tree α Int
-
-
numprod :: Prod -> (Int, String)
-
-
openSrc :: Maybe String -> String -> IO (Exception BufferedReader)
-
-
pracase :: Show a => String -> ListKV Int a -> PrintWriter -> Mutable PrintWriterS RealWorld
-
-
printgos :: ListKV Int (ListKV Int Int) -> PrintWriter -> Mutable PrintWriterS RealWorld
-
create frege code for go tabs
-
printpr :: Appendable α => Maybe β -> [YYState] -> ListKV Int String -> Mutable α γ -> ST γ ()
-
-
printreds :: (Appendable β, Show α) => ListKV α String -> Mutable β γ -> Mutable β γ
-
-
printstates :: Appendable β => [YYState] -> Mutable β α -> Mutable β α
-
-
recoveries :: Map α => α String String -> [YYState] -> ListKV Int String
-
-
ressource :: Maybe α -> String
-
-
scanlines :: [String] -> ([String], ListKV Int [String])
-
-
scanytablines :: [String] -> ([String], [String], ListKV Int String, ListKV String String, Tree String String)
-
-
sortfst :: Ord γ => (γ, β) -> (γ, α) -> Bool
-
-
sortgos :: (Ord α, Ord δ) => (δ, β, α) -> (δ, γ, α) -> Ordering
-
-
uncr :: String -> String
-
remove carriage returns from strings
-
yygenpar :: Maybe a -> IO [String]
-
-
Tree String String -> [String] -> String
-
compiletypes
-
(Int, [String]) -> YYState
-
mkState
-
InputStream -> IO [String]
-
loadInputStream
-
URL -> IO [String]
-
loadUrl
-
Maybe String -> String -> IO (Exception BufferedReader)
-
openSrc
-
String -> InputStream -> IO (Exception BufferedReader)
-
brFromIS
-
String -> IO [String]
-
fileContent
-
String -> String
-
uncr
-
String -> Item
-
Item.T, Item.NT, Item.Lit
-
ListKV Int (ListKV Int Int) -> PrintWriter -> Mutable PrintWriterS RealWorld
-
printgos
-
[String] -> ([String], [String], ListKV Int String, ListKV String String, Tree String String)
-
scanytablines
-
[String] -> ([String], ListKV 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] -> ListKV Int (ListKV Int Int)
-
altgotos2
-
[Prod] -> YYState -> (Int, ListKV Int Int)
-
gengotos2
-
[Prod] -> YYState -> [(Int, Int, Int)]
-
gengotos1
-
[Todo] -> String -> String
-
Show_Todo.showList
-
[YYState] -> String -> String
-
Show_YYState.showList
-
[YYState] -> ListKV Int String
-
actions, eactions
-
[YYState] -> [Prod]
-
extrrules
-
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] -> ListKV Int Int -> ListKV Int Int
-
gengoto2
-
Action -> String
-
Show_Action.show, Show_Action.display, Show_Action.showsub
-
Item -> Item -> Bool
-
Eq_Item./=, Eq_Item.!=, Eq_Item.==, Ord_Item.>, Ord_Item.<=, Ord_Item.<, Ord_Item.>=
-
Item -> Item -> Ordering
-
Ord_Item.<=>, Ord_Item.compare
-
Item -> Item -> Item
-
Ord_Item.max, Ord_Item.min
-
Item -> String
-
niceitem, Show_Item.show, Show_Item.display, Show_Item.showsub
-
Item -> Int
-
Eq_Item.hashCode
-
Prod -> Prod -> Bool
-
Eq_Prod./=, Eq_Prod.!=, Eq_Prod.==, Ord_Prod.>, Ord_Prod.<=, Ord_Prod.<, Ord_Prod.>=
-
Prod -> Prod -> Ordering
-
Ord_Prod.<=>, Ord_Prod.compare
-
Prod -> Prod -> Prod
-
Ord_Prod.max, Ord_Prod.min
-
Prod -> (Int, String)
-
numprod
-
Prod -> String
-
genrule, Show_Prod.show, Show_Prod.display, Show_Prod.showsub
-
Prod -> Int
-
Eq_Prod.hashCode
-
Todo -> Item -> Int -> Action
-
Action.A
-
Todo -> String
-
Show_Todo.show, Show_Todo.display, Show_Todo.showsub
-
YYState -> String
-
genst, Show_YYState.show, Show_YYState.display, Show_YYState.showsub
-
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
-
(α->Bool) -> [α] -> [α]
-
grep
-
Either α InputStreamReader -> IO (Either α BufferedReader)
-
brFromISR
-
Maybe a -> URLClassLoader -> IO [String]
-
loadRessource
-
Maybe a -> IO [String]
-
yygenpar
-
Maybe α -> Prod -> ListKV Int String -> String
-
genprod
-
Maybe α -> String
-
ressource
-
α -> Action -> [Prod] -> [(α, Int, Int)]
-
gengoto1
-
Map α => α String String -> [YYState] -> ListKV Int String
-
recoveries
-
Ord α => Int -> [α] -> Tree α Int -> Tree α Int
-
numbertypes
-
Show a => String -> ListKV Int a -> PrintWriter -> Mutable PrintWriterS RealWorld
-
pracase
-
Show α => (α, String) -> String
-
listred
-
Show α => Maybe α -> String -> IO ()
-
mainIO
-
Show α => α -> [Prod] -> Action -> String
-
genstate
-
Show α => α -> Prod -> String
-
genacc
-
Appendable β => [YYState] -> Mutable β α -> Mutable β α
-
printstates
-
ListLike α => α β -> α β -> α β
-
append
-
Appendable α => Maybe β -> [YYState] -> ListKV Int String -> Mutable α γ -> ST γ ()
-
printpr
-
(Appendable β, Show α) => ListKV α String -> Mutable β γ -> Mutable β γ
-
printreds
-
Ord γ => (γ, β) -> (γ, α) -> Bool
-
sortfst
-
Monad m => (r->m r) -> (a->r->m r) -> [a] -> r -> m r
-
fio
-
(Ord α, Ord δ) => (δ, β, α) -> (δ, γ, α) -> Ordering
-
sortgos
-
(Show γ, Show α, Show δ, Ord α, Ord δ, Ord γ, ListSource β) => β (γ, α, δ) -> String
-
gengos
