From 0981b9d6a12bd7aadbf9286459e033ac1a2ba910 Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Tue, 12 Oct 2010 07:35:08 +0000 Subject: Ok, libbu++ compiles again, the basic parser system is getting there, I think, it's still a little tricky becasue you have to do the non-terminal prime seperation yourself (I forget what it's really called), but it's going quite well. After a few tweaks to the core of it, we should be able to do some math :) --- src/lexer.cpp | 2 +- src/lexer.h | 8 +++-- src/parser.cpp | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++++ src/parser.h | 70 +++++++++++++++++++++++++++++++++++++-- src/tools/parser.cpp | 79 ++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 246 insertions(+), 6 deletions(-) diff --git a/src/lexer.cpp b/src/lexer.cpp index c7a6fcb..af9a23f 100644 --- a/src/lexer.cpp +++ b/src/lexer.cpp @@ -13,7 +13,7 @@ Bu::Lexer::Token::Token() : { } -Bu::Lexer::Token::Token( int iToken ) : +Bu::Lexer::Token::Token( Bu::Lexer::TokenType iToken ) : iToken( iToken ) { } diff --git a/src/lexer.h b/src/lexer.h index 37d268f..5847269 100644 --- a/src/lexer.h +++ b/src/lexer.h @@ -19,19 +19,21 @@ namespace Bu Lexer(); virtual ~Lexer(); + typedef int32_t TokenType; + class Token { public: Token(); - Token( int iToken ); + Token( TokenType iToken ); template - Token( int iToken, const t &v ) : + Token( TokenType iToken, const t &v ) : iToken( iToken ), vExtra( v ) { } - int iToken; + TokenType iToken; Bu::Variant vExtra; }; diff --git a/src/parser.cpp b/src/parser.cpp index 7015070..e8e8ff2 100644 --- a/src/parser.cpp +++ b/src/parser.cpp @@ -41,3 +41,96 @@ void Bu::Parser::parse() } } +void Bu::Parser::setRootNonTerminal( int iRoot ) +{ + iRootNonTerminal = iRoot; +} + +void Bu::Parser::setRootNonTerminal( const Bu::FString &sRoot ) +{ + setRootNonTerminal( hNonTerminalName.get( sRoot ) ); +} + +int Bu::Parser::addNonTerminal( const Bu::FString &sName, NonTerminal &nt ) +{ + int iId = aNonTerminal.getSize(); + aNonTerminal.append( nt ); + hNonTerminalName.insert( sName, iId ); + return iId; +} + +int Bu::Parser::addNonTerminal( const Bu::FString &sName ) +{ + int iId = aNonTerminal.getSize(); + aNonTerminal.append( NonTerminal() ); + hNonTerminalName.insert( sName, iId ); + return iId; +} + +void Bu::Parser::setNonTerminal( const Bu::FString &sName, NonTerminal &nt ) +{ + aNonTerminal[hNonTerminalName.get(sName)] = nt; +} + +int Bu::Parser::getNonTerminalId( const Bu::FString &sName ) +{ + return hNonTerminalName.get( sName ); +} + +int Bu::Parser::addReduction( const Bu::FString &sName, const Reduction &r ) +{ + int iId = aReduction.getSize(); + aReduction.append( r ); + hReductionName.insert( sName, iId ); + return iId; +} + +int Bu::Parser::addReduction( const Bu::FString &sName ) +{ + int iId = aReduction.getSize(); + aReduction.append( Reduction() ); + hReductionName.insert( sName, iId ); + return iId; +} + +void Bu::Parser::setReduction( const Bu::FString &sName, const Reduction &r ) +{ + aReduction[hReductionName.get(sName)] = r; +} + +int Bu::Parser::getReductionId( const Bu::FString &sName ) +{ + return hReductionName.get( sName ); +} + +// +// Bu::Parser::State +// + +Bu::Parser::State::State( Bu::Parser::State::Type eType, int iIndex ) : + eType( eType ), + iIndex( iIndex ) +{ +} + +Bu::Parser::State::~State() +{ +} + +// +// Bu::Parser::NonTerminal +// + +Bu::Parser::NonTerminal::NonTerminal() +{ +} + +Bu::Parser::NonTerminal::~NonTerminal() +{ +} + +void Bu::Parser::NonTerminal::addProduction( Production p ) +{ + lProduction.append( p ); +} + diff --git a/src/parser.h b/src/parser.h index 26b15a6..e720e54 100644 --- a/src/parser.h +++ b/src/parser.h @@ -1,8 +1,12 @@ #ifndef BU_PARSER_H #define BU_PARSER_H -#include "bu/list.h" #include "bu/fstring.h" +#include "bu/list.h" +#include "bu/array.h" +#include "bu/hash.h" +#include "bu/signals.h" + #include "bu/lexer.h" namespace Bu @@ -35,13 +39,75 @@ namespace Bu */ void parse(); + void setRootNonTerminal( int iRoot ); + void setRootNonTerminal( const Bu::FString &sRoot ); + + typedef Bu::Signal1 Reduction; + + /** + * Represents a possible state, either a terminal or non-terminal symbol + * in a Production. + */ + class State + { + public: + enum Type + { + typeTerminal, + typeTerminalPush, + typeNonTerminal, + typeReduction + }; + + State( Type eType, int iIndex ); + virtual ~State(); + + private: + Type eType; + int iIndex; + }; + + typedef Bu::List Production; + + class NonTerminal + { + public: + NonTerminal(); + virtual ~NonTerminal(); + + void addProduction( Production p ); + + private: + typedef Bu::List ProductionList; + ProductionList lProduction; + }; + + int addNonTerminal( const Bu::FString &sName, NonTerminal &nt ); + int addNonTerminal( const Bu::FString &sName ); + void setNonTerminal( const Bu::FString &sName, NonTerminal &nt ); + int getNonTerminalId( const Bu::FString &sName ); + + int addReduction( const Bu::FString &sName, const Reduction &r ); + int addReduction( const Bu::FString &sName ); + void setReduction( const Bu::FString &sName, const Reduction &r ); + int getReductionId( const Bu::FString &sName ); + private: typedef Bu::List LexerStack; typedef Bu::List TokenStack; - typedef Bu::List StateStack; + typedef Bu::List StateStack; + typedef Bu::Array ReductionArray; + typedef Bu::Hash NameIndexHash; + typedef Bu::Array NonTerminalArray; + LexerStack sLexer; TokenStack sToken; StateStack sState; + ReductionArray aReduction; + NameIndexHash hReductionName; + NonTerminalArray aNonTerminal; + NameIndexHash hNonTerminalName; + int iRootNonTerminal; }; }; diff --git a/src/tools/parser.cpp b/src/tools/parser.cpp index a70dfa4..e4fc95f 100644 --- a/src/tools/parser.cpp +++ b/src/tools/parser.cpp @@ -149,12 +149,91 @@ private: QueueBuf qbIn; }; +void redAdd( Bu::Parser &p ) +{ +} + +void redPrint( Bu::Parser &p ) +{ +} + int main( int argc, char *argv[] ) { File fIn( argv[1], File::Read ); Parser p; + { + Parser::NonTerminal nt; + int iSelf = p.addNonTerminal("expr"); + nt.addProduction( + Parser::Production( + Parser::State( + Parser::State::typeTerminal, + tokPlus + ) + ).append( + Parser::State( + Parser::State::typeNonTerminal, + iSelf + ) + ).append( + Parser::State( + Parser::State::typeReduction, + p.addReduction("add") + ) + ) + ); + nt.addProduction( + Parser::Production() + ); + p.addNonTerminal( "expr", nt ); + } + { + Parser::NonTerminal nt; + nt.addProduction( + Parser::Production( + Parser::State( + Parser::State::typeTerminalPush, + tokNumber + ) + ).append( + Parser::State( + Parser::State::typeNonTerminal, + p.getNonTerminalId("expr") + ) + ) + ); + p.addNonTerminal( "expr'", nt ); + } + { + Parser::NonTerminal nt; + nt.addProduction( + Parser::Production( + Parser::State( + Parser::State::typeNonTerminal, + p.getNonTerminalId("expr'") + ) + ).append( + Parser::State( + Parser::State::typeTerminal, + tokCompute + ) + ).append( + Parser::State( + Parser::State::typeReduction, + p.addReduction("print") + ) + ) + ); + p.addNonTerminal("input", nt ); + } + + p.setRootNonTerminal("input"); + + p.setReduction("add", Bu::slot( &redAdd ) ); + p.setReduction("print", Bu::slot( &redPrint ) ); + p.pushLexer( new MathLexer( fIn ) ); p.parse(); -- cgit v1.2.3