Is this an ambiguous grammar? How to resolve it?

Question

To preface to this, my knowledge of such things is small.

In any case, I am developing a context-free grammar to describe the structure of algebraic expressions so that I can teach myself how the CYK parsing algorithm works. I understand how such a structure can only work with infix algebraic expressions, but I cannot figure out how to develop a grammar that can handle both unary and binary definitions of the "-" operator.

For reference, here is the grammar I wrote (where S is the start character) in CNF:

S → x
A → OS
S → LB
B → SR
S → KS
O → +
O → -
O → *
O → /
O → ^
K → -
L → (
R →)

The problem is that how can the CYK parsing algorithm know in advance whether to choose between S → KS and A → OS when it encounters the "-" operator? Is such a grammatical context free? And most importantly, since programming languages ​​can process languages ​​with a binary and unary minus sign, how should I reasonably parse this?

Answer 1

, , , CYK OCaml, :)

3- -4, , S -> K S -4, A -> O S - -4. S . , , , A, , S, , , S -> S O S.

, CYK, - , " ", . CYK, -4 S -> K S, - S -> K S, -. , 3 S, , , . , , - S -> O S .

, , - , , . !

Answer 2

, , .

, :

S -> EXPR
EXPR -> (EXPR)
EXPR -> - EXPR
EXPR -> EXPR + EXPR
EXPR -> EXPR - EXPR
// etc...

Answer 3

, , . , :

a + b + c . , +. , , : , , .

a + b * c . , .

(a + bc), , , .

unary subtraction is problematic, as you say.

If we want to solve these problems, but still have a quick analysis grammar for algebra, one approach is to have different EXPR “levels”, one for each level of binding required by the priority levels. For instance,

TERM -> (S)
EXPO -> TERM ^ EXPO
PROD -> PROD * EXPO
PROD -> PROD / EXPO
PROD -> -PROD
SUM -> SUM + PROD
SUM -> SUM - PROD
S -> SUM

This requires that you also enable "promotion" of types: SUM → PROD, PROD → EXP, EXP → TERM, etc., so that everything can end.

Hope this helps!