The list might be interested to see a C version of what is writen in perl
using the Thin interface.
This is the first test that is in t/thin_eq.t, doing this ambiguous grammar:
:start ::= S
S ::= E
E ::= E op E
E ::= number
applied on tokens "2", "-", "0", "*", "3", "+", "1".
Result is:
Expected result (((2-0)*3)+1) == 7, value 7
Expected result ((2-(0*3))+1) == 3, value 3
Expected result (2-((0*3)+1)) == 1, value 1
Expected result (2-(0*(3+1))) == 2, value 2
Expected result ((2-0)*(3+1)) == 8, value 8
Source files in attachment.
May I ask somebody to review it, because I plan to submit it to git for
inclusion in debian packages -;
valgrind on it is happy v.s. eventual lekage btw.
Thanks, Jean-Damien.
--
You received this message because you are subscribed to the Google Groups
"marpa parser" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <marpa.h>
#include "thin_macros.h"
/*
C version of first example in file t/thin_eq.t
from Marpa::R2 CPAN distribution
Grammar is:
:start ::= S
S ::= E
E ::= E op E
E ::= number
Expected values:
(2-(0*(3+1))) == 2 => 1
(((2-0)*3)+1) == 7 => 1
((2-(0*3))+1) == 3 => 1
((2-0)*(3+1)) == 8 => 1
(2-((0*3)+1)) == 1 => 1
Compilation: cc -g -o ./thin ./thin.c -lmarpa
Execution : ./thin
*/
/* A stack here is composed of two elements, the string and a corresponding int */
typedef struct s_stack {
char *string;
int value;
} s_stack_;
static char *_make_str (const char *fmt, ...);
static void _check (Marpa_Error_Code errorCode, const char *call, int forcedCondition);
static void _push_to_stack(s_stack_ **stackpp, int *stacksizep, int index, char *string, int value);
struct marpa_error_description_s {
Marpa_Error_Code error_code;
const char*name;
const char*suggested;
};
extern const struct marpa_error_description_s marpa_error_description[];
int main() {
Marpa_Config marpa_configuration;
Marpa_Grammar g;
Marpa_Symbol_ID S, E, op, number;
Marpa_Rule_ID start_rule_id, op_rule_id, number_rule_id;
Marpa_Recognizer r;
char *token_values[] = { "0", "1", "2", "3", "0", "-", "+", "*" };
s_stack_ expected_results[5] = {
{"(2-(0*(3+1))) == 2", 2},
{"(((2-0)*3)+1) == 7", 7},
{"((2-(0*3))+1) == 3", 3},
{"((2-0)*(3+1)) == 8", 8},
{"(2-((0*3)+1)) == 1", 1}
};
int ivalue = 0;
Marpa_Earley_Set_ID latest_earley_set_ID;
Marpa_Bocage bocage;
Marpa_Order order;
Marpa_Tree tree;
s_stack_ *stackp = NULL;
size_t stacksize = -1;
int zero = 4; /* Indice 4 in token_values */
int minus_token_value = 5; /* Indice 5 in token_values */
int plus_token_value = 6; /* Indice 6 in token_values */
int multiply_token_value = 7; /* Indice 7 in token_values */
/* Configuration initialisation */
marpa_c_init(&marpa_configuration); /* never fails as per the doc */
/* Grammar creation */
g = marpa_g_new(&marpa_configuration);
_check(marpa_c_error(&marpa_configuration, NULL), "marpa_g_new()", g == NULL);
/* Symbols creation */
CREATE_SYMBOL(S, g);
CREATE_SYMBOL(E, g);
CREATE_SYMBOL(op, g);
CREATE_SYMBOL(number, g);
/* ::start ::= S */
SET_START_SYMBOL(S, g);
/* Rules creation */
{Marpa_Symbol_ID rhs[] = { E }; CREATE_RULE(start_rule_id, g, S, rhs, ARRAY_LENGTH(rhs));}
{Marpa_Symbol_ID rhs[] = { E, op, E }; CREATE_RULE(op_rule_id, g, E, rhs, ARRAY_LENGTH(rhs));};
{Marpa_Symbol_ID rhs[] = { number }; CREATE_RULE(number_rule_id, g, E, rhs, ARRAY_LENGTH(rhs));}
PRECOMPUTE(g);
r = marpa_r_new(g);
if (r == NULL) {
fprintf(stderr, "marpa_r_new() failure\n");
exit(EXIT_FAILURE);
}
if (marpa_r_start_input(r) < 0) {
fprintf(stderr, "marpa_r_start_input() failure\n");
exit(EXIT_FAILURE);
}
/*
The numbers from 1 to 3 are themselves --
that is, they index their own token value.
Important: zero cannot be itself!
*/
ALTERNATIVE(r, number, 2, 1);
EARLEME_COMPLETE(r);
ALTERNATIVE(r, op, minus_token_value, 1);
EARLEME_COMPLETE(r);
ALTERNATIVE(r, number, zero, 1);
EARLEME_COMPLETE(r);
ALTERNATIVE(r, op, multiply_token_value, 1);
EARLEME_COMPLETE(r);
ALTERNATIVE(r, number, 3, 1);
EARLEME_COMPLETE(r);
ALTERNATIVE(r, op, plus_token_value, 1);
EARLEME_COMPLETE(r);
ALTERNATIVE(r, number, 1, 1);
EARLEME_COMPLETE(r);
latest_earley_set_ID = marpa_r_latest_earley_set(r);
bocage = marpa_b_new(r, latest_earley_set_ID);
if (bocage == NULL) {
fprintf(stderr, "marpa_b_new() failure\n");
exit(EXIT_FAILURE);
}
order = marpa_o_new(bocage);
if (order == NULL) {
fprintf(stderr, "marpa_o_new() failure\n");
exit(EXIT_FAILURE);
}
tree = marpa_t_new(order);
if (tree == NULL) {
fprintf(stderr, "marpa_t_new() failure\n");
exit(EXIT_FAILURE);
}
while (1) {
int itree = marpa_t_next(tree);
int nextok = 1;
Marpa_Value valuator;
if (itree < 0) {
break;
}
if ((valuator = marpa_v_new(tree)) == NULL) {
fprintf(stderr, "marpa_v_new() failure\n");
exit(EXIT_FAILURE);
}
marpa_v_symbol_is_valued_set(valuator, op_rule_id, 1);
marpa_v_symbol_is_valued_set(valuator, start_rule_id, 1);
marpa_v_symbol_is_valued_set(valuator, number_rule_id, 1);
while (nextok) {
Marpa_Step_Type type = marpa_v_step(valuator);
Marpa_Rule_ID rule_id;
switch (type) {
case MARPA_STEP_TOKEN:
{
Marpa_Symbol_ID token_id = marpa_v_token(valuator);
int token_value_ix = marpa_v_token_value(valuator);
int arg_n = marpa_v_result(valuator);
PUSH_TO_STACK(arg_n, strdup(token_values[token_value_ix]), atoi(token_values[token_value_ix]));
break;
}
case MARPA_STEP_RULE:
{
Marpa_Rule_ID rule_id = marpa_v_rule(valuator);
int arg_0 = marpa_v_arg_0(valuator);
int arg_n = marpa_v_arg_n(valuator);
if (rule_id == start_rule_id) {
PUSH_TO_STACK(arg_0, _make_str("%s == %d", stackp[arg_n].string, stackp[arg_n].value), stackp[arg_n].value);
}
else if (rule_id == number_rule_id) {
PUSH_TO_STACK(arg_0, _make_str("%d", stackp[arg_0].value), stackp[arg_0].value);
}
else if (rule_id == op_rule_id) {
char *left_string = stackp[arg_0].string;
int left_value = stackp[arg_0].value;
char *op = stackp[arg_0 + 1].string;
char *right_string = stackp[arg_n].string;
int right_value = stackp[arg_n].value;
int value;
char *text = _make_str("(%s%s%s)", left_string, op, right_string);
switch (*op) {
case '+':
PUSH_TO_STACK(arg_0, text, left_value + right_value);
break;
case '-':
PUSH_TO_STACK(arg_0, text, left_value - right_value);
break;
case '*':
PUSH_TO_STACK(arg_0, text, left_value * right_value);
break;
default:
fprintf(stderr, "Unknown op %s\n", op);
exit(EXIT_FAILURE);
}
} else {
fprintf(stderr, "Unknown rule %d\n", rule_id);
exit(EXIT_FAILURE);
}
break;
}
case MARPA_STEP_INACTIVE:
nextok = 0;
break;
default:
fprintf(stderr, "Unexpected type %d\n", type);
exit(EXIT_FAILURE);
}
}
/* Check result and free the stack */
if (stacksize < 0) {
fprintf(stderr, "No result !?\n");
} else {
int i;
s_stack_ *expected_resultp = NULL;
for (i = 0; i <= ARRAY_LENGTH(expected_results); i++) {
if (strcmp(expected_results[i].string, stackp[0].string) == 0) {
expected_resultp = &(expected_results[i]);
}
}
if (expected_resultp == NULL) {
fprintf(stderr, "Totally unexpected result %s, value %d\n", stackp[0].string, stackp[0].value);
} else {
if (expected_resultp->value == stackp[0].value) {
fprintf(stderr, "Expected result %s, value %d\n", expected_resultp->string, expected_resultp->value);
} else {
fprintf(stderr, "Unexpected result %s, value %d instead of %d\n", stackp[0].string, stackp[0].value, expected_resultp->value);
}
}
for (i = 0; i <= stacksize; i++) {
free(stackp[i].string);
stackp[i].string = NULL;
}
free(stackp);
stackp = NULL;
stacksize = -1;
}
/* Free valuator */
marpa_v_unref(valuator);
}
/* Free marpa */
marpa_t_unref(tree);
marpa_o_unref(order);
marpa_b_unref(bocage);
marpa_r_unref(r);
marpa_g_unref(g);
exit(EXIT_SUCCESS);
}
/* Copied almost verbatim from snprintf man page on Linux */
static char *_make_str(const char *fmt, ...) {
int n;
int size = 100; /* Guess we need no more than 100 bytes */
char *p, *np;
va_list ap;
p = malloc(size);
if (p == NULL) {
fprintf(stderr, "malloc() failure\n");
exit(EXIT_FAILURE);
}
while (1) {
/* Try to print in the allocated space */
va_start(ap, fmt);
n = vsnprintf(p, size, fmt, ap);
va_end(ap);
/* Check error code */
if (n < 0) {
free(p);
fprintf(stderr, "vsnprintf() failure\n");
exit(EXIT_FAILURE);
}
/* If that worked, return the string */
if (n < size) {
return p;
}
/* Else try again with more space */
size = n + 1; /* Precisely what is needed */
np = realloc(p, size);
if (np == NULL) {
free(p);
fprintf(stderr, "realloc() failure\n");
exit(EXIT_FAILURE);
} else {
p = np;
}
}
}
static void _check(Marpa_Error_Code errorCode, const char *call, int forcedCondition) {
if (forcedCondition != 0 || errorCode != MARPA_ERR_NONE) {
const char *function = (call != NULL) ? call : "<unknown>";
const char *msg = (errorCode >= 0 && errorCode < MARPA_ERROR_COUNT) ? marpa_error_description[errorCode].name : "Generic error";
fprintf(stderr,"%s: %s", function, msg);
exit(EXIT_FAILURE);
}
}
static void _push_to_stack(s_stack_ **stackpp, int *stacksizep, int index, char *string, int value) {
s_stack_ *stackp = *stackpp;
int stacksize = *stacksizep;
if (stacksize < index) {
if (stacksize < 0) {
stackp = malloc(sizeof(s_stack_));
} else {
stackp = realloc(stackp, sizeof(s_stack_) * (index + 1));
}
stacksize = index;
}
if (stackp == NULL) {
exit(EXIT_FAILURE);
}
if (stackp[index].string != NULL) {
free(stackp[index].string);
}
stackp[index].string = string;
stackp[index].value = value;
*stacksizep = stacksize;
*stackpp = stackp;
}
#ifndef THIN_MACROS_H
#define THIN_MACROS_H
#define ARRAY_LENGTH(array) (sizeof((array))/sizeof((array)[0]))
#define CREATE_SYMBOL(symbolId, grammar) { \
marpa_g_error_clear(grammar); \
symbolId = marpa_g_symbol_new(grammar); \
_check(marpa_g_error(grammar, NULL), "marpa_g_symbol_new()", symbolId < 0); \
}
#define CREATE_RULE(ruleId, grammar, ...) { \
marpa_g_error_clear(grammar); \
ruleId = marpa_g_rule_new(grammar, __VA_ARGS__); \
_check(marpa_g_error(grammar, NULL), "marpa_g_rule_new()", ruleId < 0); \
}
#define SET_START_SYMBOL(symbolId, grammar) { \
marpa_g_error_clear(grammar); \
int result = marpa_g_start_symbol_set(grammar, symbolId); \
_check(marpa_g_error(grammar, NULL), "marpa_g_start_symbol_set()", result < 0); \
}
#define PRECOMPUTE(grammar) { \
int result; \
marpa_g_error_clear(grammar); \
result = marpa_g_precompute(grammar); \
_check(marpa_g_error(grammar, NULL), "marpa_g_precompute()", result < 0); \
}
#define ALTERNATIVE(r, token_id, value, length) { \
int result = marpa_r_alternative (r, token_id, value, length); \
if (result != MARPA_ERR_NONE) { \
fprintf(stderr, "marpa_r_alternative() failure, error code %d", result); \
} \
}
#define EARLEME_COMPLETE(r) { \
Marpa_Earleme result = marpa_r_earleme_complete(r); \
if (result < 0) { \
fprintf(stderr, "marpa_r_earleme_complete() failure, error code %d", result); \
} \
}
#define PUSH_TO_STACK(index, str, val) { \
_push_to_stack(&stackp, &stacksize, (index), (str), (val)); \
}
#endif /* THIN_MACROS_H */
