Package frege.tools.YYgen

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

Instances

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 Types

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]

Functions and Values

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]

Functions and Values by Type

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

Valid HTML 4.01 Strict