Skip to content

Instantly share code, notes, and snippets.

@nomunomu0504

nomunomu0504/digit.cpp

Last active December 27, 2022 00:31
Show Gist options
  • Save nomunomu0504/b36f1ae76263f20808515cbf41fb3523 to your computer and use it in GitHub Desktop.
Save nomunomu0504/b36f1ae76263f20808515cbf41fb3523 to your computer and use it in GitHub Desktop.
Download ZIP
再帰下降法のC言語パーサーもどき
Raw
digit.cpp
/**
* ## 数値 ##
* DIGIT ::= [0-9]+
* ;
*
* @param pc
* @param endp
* @return
*/
int digit( const char* pc, const char** endp ) {
// 数値文字列の変数
string number;
*endp = pc;
// 数字が続くだけ続ける
while ( true ) {
if ( isdigit(**endp) )
{
// 文字列に追加
number.push_back(**endp);
// カウンタをインクリメント
*endp += 1;
}
else if ( isspace(**endp) )
{
*endp += 1;
}
else if ( ('_' == **endp) || isalnum(**endp) ) {
return variable( pc, endp );
}
else break;
}
// 数値文字列が空かどうか
if (number.empty()) {
// 空なら0を返す
return 0;
} else {
// 0以外は数値を返す
return stoi(number);
}
}
Raw
expr.cpp
/**
* ## 式は項のみ or (+, -)演算子を含む式 ##
* expr ::= term
* | expr (+|-) term
* ;
*
* @param pc 解析する文字列の先頭
* @param endp 解析が終わった場所
* @return 計算結果
*/
int expr( const char* pc, const char** endp ) {
// 1文字目（必ずtermに属する）を取得する
int left = term( pc, endp );
while( true ) {
if ('+' == **endp)
{
// ＋1は '+' 分ずらす
int right = term( *endp + 1, endp );
left += right;
}
else if ('-' == **endp)
{
// ＋1は '-' 分ずらす
int right = term( *endp + 1, endp );
left -= right;
}
else if (isspace(**endp))
{
*endp += 1;
} else { break; }
}
return left;
}
Raw
factor.cpp
/**
* ## 因子は数値 or カッコを含む（式, 項）or 演算子を含む##
* factor ::= DIGIT
* | VARIABLE
* | VARIABLE OPERATOR expr
* | '(' expr ')'
* ;
*
* @param pc 解析する文字列の先頭
* @param endp 解析が終わった場所
* @return 計算結果
*/
int factor( const char* pc, const char** endp ) {
*endp = pc;
while (true) {
if ('(' == **endp) {
// カッコ分読み飛ばし
*endp += 1;
// カッコ内の式を解析
int innerExprValue = expr(*endp, endp);
// カッコとじまでポインタを進める
while (true) {
// カッコ閉じなら
if (')' == **endp) {
// カッコ分飛ばし
(*endp)++;
// pcに文字列コピー
pc = *endp;
// カッコ内の演算結果を文字列に
string valstr = to_string(innerExprValue);
char *cstr = new char[valstr.size() + 1]; // メモリ確保
strcpy(cstr, valstr.c_str()); // コピー
// 現在の文字列の先頭に計算結果を連結
char *tmps = strcat(cstr, pc);
// tmp文字列用のメモリ開放
delete[] cstr; // メモリ解放
// 連結後の文字列をpcに代入
pc = tmps;
// 解析済み文字列にも同様のものを代入
*endp = pc;
// 残りの数式の解析
int tmp = expr(pc, endp);
// 演算結果を返す
return tmp;
} else {
*endp += 1;
}
}
} else if (isspace(**endp)) {
(*endp)++;
} else if (isdigit(**endp)) {
return digit(pc, endp);
} else if (isalpha(**endp)) {
return variable(pc, endp);
} else {
return expr(pc, endp);
}
}
}
Raw
main.cpp
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <iostream>
#include <sstream>
#include <string>
#include <map>
using namespace std;
/**
* バッカス記法(BNF) （ +, -, *, /, '(', ')' ）
* 左辺と同じ非終端記号が右辺先頭にくると「左再帰性」になる
*
* ## 式は項のみ or (+, -)演算子を含む式 ##
* expr ::= term, [(+|-) term]*
* ;
*
* ## 項は因子 or (*, /)演算子を含む項 ##
* term ::= factor [(*|/|%) factor]*
* ;
*
* ## 因子は数値 or カッコを含む（式, 項）or 演算子を含む##
* factor ::= DIGIT
* | VARIABLE
* | VARIABLE OPERATOR expr
* | '(' expr ')'
* ;
*
* ## 数値 ##
* DIGIT ::= [0-9]+ ;
*
* ## 変数名 ##
* VARIABLE ::= _a-zA-Z [_a-zA-Z0-9]+ ;
*
* ## 演算子 ##
* OPERATOR ::= '='
*/
int expr( const char* , const char** );
int term( const char* , const char** );
int factor( const char* , const char** );
int digit( const char* , const char** );
int variable( const char* , const char** );
// 変数展開用の変数定義
map<string, int> varStack;
/**
* ## 式は項のみ or (+, -)演算子を含む式 ##
* expr ::= term
* | expr (+|-) term
* ;
*
* @param pc 解析する文字列の先頭
* @param endp 解析が終わった場所
* @return 計算結果
*/
int expr( const char* pc, const char** endp ) {
// 1文字目（必ずtermに属する）を取得する
int left = term( pc, endp );
while( true ) {
if ('+' == **endp)
{
// ＋1は '+' 分ずらす
int right = term( *endp + 1, endp );
left += right;
}
else if ('-' == **endp)
{
// ＋1は '-' 分ずらす
int right = term( *endp + 1, endp );
left -= right;
}
else if (isspace(**endp))
{
*endp += 1;
} else { break; }
}
return left;
}
/**
* ## 項は因子 or (*, /, '%')演算子を含む項 ##
* term ::= factor
* | term (*|/|%) factor
* ;
*
* @param pc 解析する文字列の先頭
* @param endp 解析が終わった場所
* @return 計算結果
*/
int term( const char* pc, const char** endp ) {
// 1文字目（必ずfactorに属する）を取得する
int left = factor( pc, endp );
while( true ) {
if ('*' == **endp)
{
// ＋1は '*' 分ずらす
int right = factor( *endp + 1, endp );
left *= right;
}
else if ('/' == **endp)
{
// ＋1は '/' 分ずらす
int right = factor( *endp + 1, endp );
left /= right;
}
else if ('%' == **endp)
{
// ＋1は '%' 分ずらす
int right = factor( *endp + 1, endp );
left %= right;
}
else if (isspace(**endp))
{
*endp += 1;
}
else { break; }
}
return left;
}
/**
* ## 因子は数値 or カッコを含む（式, 項）or 演算子を含む##
* factor ::= DIGIT
* | VARIABLE
* | VARIABLE OPERATOR expr
* | '(' expr ')'
* ;
*
* @param pc 解析する文字列の先頭
* @param endp 解析が終わった場所
* @return 計算結果
*/
int factor( const char* pc, const char** endp ) {
*endp = pc;
while (true) {
if ('(' == **endp) {
// カッコ分読み飛ばし
*endp += 1;
// カッコ内の式を解析
int innerExprValue = expr(*endp, endp);
// カッコとじまでポインタを進める
while (true) {
// カッコ閉じなら
if (')' == **endp) {
// カッコ分飛ばし
(*endp)++;
// pcに文字列コピー
pc = *endp;
// カッコ内の演算結果を文字列に
string valstr = to_string(innerExprValue);
char *cstr = new char[valstr.size() + 1]; // メモリ確保
strcpy(cstr, valstr.c_str()); // コピー
// 現在の文字列の先頭に計算結果を連結
char *tmps = strcat(cstr, pc);
// tmp文字列用のメモリ開放
delete[] cstr; // メモリ解放
// 連結後の文字列をpcに代入
pc = tmps;
// 解析済み文字列にも同様のものを代入
*endp = pc;
// 残りの数式の解析
int tmp = expr(pc, endp);
// 演算結果を返す
return tmp;
} else {
*endp += 1;
}
}
} else if (isspace(**endp)) {
(*endp)++;
} else if (isdigit(**endp)) {
return digit(pc, endp);
} else if (isalpha(**endp)) {
return variable(pc, endp);
} else {
return expr(pc, endp);
}
}
}
/**
* ## 数値 ##
* DIGIT ::= [0-9]+
* ;
*
* @param pc
* @param endp
* @return
*/
int digit( const char* pc, const char** endp ) {
// 数値文字列の変数
string number;
*endp = pc;
// 数字が続くだけ続ける
while ( true ) {
if ( isdigit(**endp) )
{
// 文字列に追加
number.push_back(**endp);
// カウンタをインクリメント
*endp += 1;
}
else if ( isspace(**endp) )
{
*endp += 1;
}
else if ( ('_' == **endp) || isalnum(**endp) ) {
return variable( pc, endp );
}
else break;
}
// 数値文字列が空かどうか
if (number.empty()) {
// 空なら0を返す
return 0;
} else {
// 0以外は数値を返す
return stoi(number);
}
}
/**
* ## 変数名 ##
* VARIABLE ::= _a-zA-Z [_a-zA-Z0-9]+ ;
*/
int variable( const char* pc, const char** endp ) {
// 変数名の取得
string name;
*endp = pc;
// 変数名を１文字ずつ取得
while ( true ) {
// 変数名かどうか
if (isdigit(*pc)) {
printf("Error. variant first letter must not number.");
exit(0);
}
if ( ('_' == **endp) || isalnum(**endp) )
{
// 文字列に追加
name.push_back(**endp);
*endp += 1;
}
else if ( isspace(**endp) ) {
*endp += 1;
}
else break;
}
// 変数名が空かどうか
if (name.empty()) {
//　空なら0を返しておく
return 0;
}
else {
if ('=' == **endp) {
// '='の分を進める
*endp += 1;
pc = *endp;
int result = expr(pc, endp);
varStack[name] = result;
return varStack[name];
}
else
{
// 変数スタックにキー[name]が登録されていない
if (varStack.find(name) == varStack.end() ) {
printf("Variant %s is undefined.\n", name.c_str());
} else {
// 登録されている
return varStack[name];
}
}
}
}
/**
*
* @param p0 計算結果
* @param p1 計算期待値
*/
void print(int ExpectedValue, int CalculatedValue) {
printf("Result: %s\n"
" -- ExpectedValue: %d, CalculatedValue: %d\n",
(CalculatedValue == ExpectedValue) ? "True" : "False",
ExpectedValue,
CalculatedValue);
}
int main() {
// 計算結果保持変数
int res;
// 一括代入（右結合の確認）
const char *test = nullptr;
expr("tx = ty = tz = 6", &test);
printf("\n== 一括代入（右結合の確認）tx ==\n");
test = nullptr;
res = expr("tx", &test);
print(6, res);
printf("\n== 一括代入（右結合の確認）ty ==\n");
test = nullptr;
res = expr("ty", &test);
print(6, res);
printf("\n== 一括代入（右結合の確認）tz ==\n");
test = nullptr;
res = expr("tz", &test);
print(6, res);
// 20 - 単純な計算 : OK
printf("\n== 単純な計算 ==\n");
const char *one = nullptr;
res = expr("1+2*5+9", &one);
print(20, res);
// 100 - 複数桁の単純な計算 : OK
printf("\n== 複数桁の単純な計算 ==\n");
const char *two = nullptr;
res = expr("10+20+10+30*2", &two);
print(100, res);
// 35 - カッコを含む計算 : OK
printf("\n== カッコを含む計算 ==\n");
const char *three = nullptr;
res = expr("(2*5)+5*2+15", &three);
print(35, res);
// 50 - 複数のカッコを含む計算 : OK
printf("\n== 複数のカッコを含む計算 ==\n");
const char *four = nullptr;
res = expr("(2*5)+2*(5+15)", &four);
print(50, res);
// 20 - 空白を含む単純な計算 : OK
printf("\n== 空白を含む単純な計算 ==\n");
const char *five = nullptr;
res = expr("1 + 2 * 5 + 9", &five);
print(20, res);
// TODO: ネストされてると動かない
// 50 - カッコにカッコが含まれる計算 : NG
printf("\n== カッコにカッコが含まれる計算 ==\n");
const char *six = nullptr;
res = expr("(5+(1+2*2))*5", &six);
print(50, res);
// 7 - 剰余演算子を含む計算 : OK
printf("\n== 剰余演算子を含む計算 ==\n");
const char *seven = nullptr;
res = expr("5 + 5 % 3", &seven);
print(7, res);
/**
* 変数は登場順に書かないとだめ...
*/
// 5 - 複数の変数が複数個を含んだ計算 : OK
printf("\n== 複数の変数が複数個を含んだ計算 ==\n");
const char *eight = nullptr;
expr("a = 3", &eight);
eight = nullptr;
expr("b = 2", &eight);
eight = nullptr;
res = expr("a+b", &eight);
print(5, res);
// 8 - 複数の変数が複数個を含んだ計算 : OK
printf("\n== 複数の変数が複数個を含んだ計算 ==\n");
const char *nine = nullptr;
expr("c = b", &nine);
nine = nullptr;
expr("d = 1", &nine);
nine = nullptr;
res = expr("a+b+c+d", &nine);
print(8, res);
// 8 - 複数文字の変数を含んだ計算 : OK
printf("\n== 複数文字の変数を含んだ計算 ==\n");
const char *ten = nullptr;
expr("nomunomu0504 = 1", &ten);
ten = nullptr;
res = expr("9+nomunomu0504", &ten);
print(10, res);
const char *_one = nullptr;
res = expr("8/4/2", &_one);
print(1, res);
const char *_three = nullptr;
res = expr("8/4*2", &_three);
print(4, res);
const char *_four = nullptr;
res = expr("2*4/8", &_four);
print(1, res);
const char *_two = nullptr;
res = expr("1-2-3", &_two);
print(-4, res);
return 0 ;
}
/** Local Variables: **/
/** mode: c++ **/
/** End: **/
Raw
term.cpp
/**
* ## 項は因子 or (*, /, '%')演算子を含む項 ##
* term ::= factor
* | term (*|/|%) factor
* ;
*
* @param pc 解析する文字列の先頭
* @param endp 解析が終わった場所
* @return 計算結果
*/
int term( const char* pc, const char** endp ) {
// 1文字目（必ずfactorに属する）を取得する
int left = factor( pc, endp );
while( true ) {
if ('*' == **endp)
{
// ＋1は '*' 分ずらす
int right = factor( *endp + 1, endp );
left *= right;
}
else if ('/' == **endp)
{
// ＋1は '/' 分ずらす
int right = factor( *endp + 1, endp );
left /= right;
}
else if ('%' == **endp)
{
// ＋1は '%' 分ずらす
int right = factor( *endp + 1, endp );
left %= right;
}
else if (isspace(**endp))
{
*endp += 1;
}
else { break; }
}
return left;
}
Raw
variant.cpp
/**
* ## 変数名 ##
* VARIABLE ::= _a-zA-Z [_a-zA-Z0-9]+ ;
*/
int variable( const char* pc, const char** endp ) {
// 変数名の取得
string name;
*endp = pc;
// 変数名を１文字ずつ取得
while ( true ) {
// 変数名かどうか
if (isdigit(*pc)) {
printf("Error. variant first letter must not number.");
exit(0);
}
if ( ('_' == **endp) || isalnum(**endp) )
{
// 文字列に追加
name.push_back(**endp);
*endp += 1;
}
else if ( isspace(**endp) ) {
*endp += 1;
}
else break;
}
// 変数名が空かどうか
if (name.empty()) {
//　空なら0を返しておく
return 0;
}
else {
if ('=' == **endp) {
// '='の分を進める
*endp += 1;
pc = *endp;
int result = expr(pc, endp);
varStack[name] = result;
return varStack[name];
}
else
{
// 変数スタックにキー[name]が登録されていない
if (varStack.find(name) == varStack.end() ) {
printf("Variant %s is undefined.\n", name.c_str());
} else {
// 登録されている
return varStack[name];
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment