Rekurencyjna analiza wyrażeńNotacja BNF. Sięgając do zasobów encyklopedycznych, to:
Notacja Backusa-Naura (ang. Backus-Naur Form, BNF) – metoda zapisu reguł gramatyki bezkontekstowej.
Notacja ta jest powszechnie używana w informatyce do zapisu składni (syntaktyki) języków programowania i protokołów komunikacyjnych. Została wymyślona przez Johna Backusa w latach 50. w czasie prac nad językiem Fortran, a następnie zmodyfikowana przez Petera Naura i użyta do zdefiniowania składni języka ALGOL.
Notacja BNF jest zestawem reguł produkcji o następującej postaci:
<symbol> ::= <wyrażenie zawierające symbole>
Znaczenie użytych tu symboli jest następujące:
- lewy ogranicznik symbolu: <
- prawy ogranicznik symbolu: >
- jest zdefiniowane jako (taki jakby operator przypisania): ::=
- lub: |
Posłużmy się przykładem. Co to jest liczba całkowita?
W myśl powyższych reguł, liczba całkowita to:
<liczba całkowita>::= <znak liczby> <ciąg cyfr>
gdzie:
<znak liczby> ::= + | - |
(znak liczby to: + lub – lub puste)
gdzie:
<ciąg cyfr> ::= <cyfra> <ciąg cyfr> | <cyfra>
natomiast:
<cyfra> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Tu warto zauważyć, że definicja jest rekurencyjna. <ciąg cyfr> to jest <cyfra> i <ciąg cyfr> lub <cyfra> (rekurencja).
Nie wiem jak was, ale jak mnie uczyli na studiach Pascal'a, to myśmy „katowali” notację BNF do upadu. Wtedy wydawało mi się to bez sensu i do niczego nie przydatne. Dzisiaj widzę to trochę inaczej. Wspomniałem o notacji BNF. Jak by wyglądała definicja wyrażenia logicznego w powyższej notacji?
<wyrażenie logiczne> ::= <wyrażenie proste>
gdzie:
<wyrażenie proste> ::= <operator jednoargumentowy> <składnik> | <wyrażenie addytywne>
<operator jednoargumentowy> ::= NOT |
(jest to NOT lub puste).
Natomiast: <wyrażenie addytywne> ::= <składnik> | <składnik> <operator addytywny> <wyrażenie addytywne>
gdzie <operator addytywny> ::= OR | XOR
<składnik> ::= <czynnik> | <czynnik> <operator multiplikatywny> <czynnik>
gdzie:
<czynnik> ::= <identyfikator> | <stała logiczna> | ( <wyrażenie proste> )
<operator multiplikatywny> ::= AND
<stała logiczna> ::= TRUE | FALSE
Rozumiem, że to wygląda na pop..ne, ale w praktyce daje się realnie zastosować. Wystarczy trochę przemyśleń i staje się jasne i proste. Daleko nie szukając, analiza wyrażenia logicznego ma zdefiniowane symbole:
- IdentSy – identyfikator
- LeftParSy – nawias (
- RightParSy – nawias )
- LogicAndOpSy – AND – operator logiczny
- LogicOrOpSy – OR – operator logiczny,
- LogicExOrOpSy – XOR – operator logiczny
- LogicNotOpSy – NOT – operator logiczny
- TrueSy – stała logiczna
- FalseSy – stała logiczna.
Plus kilka innych elementów leksykalnych, które mają następujące znaczenie:
- NoSy – coś nieokreślonego, innego niż wyżej wymienione,
- EoLnSy – osiągnięto koniec analizowanego wiersza.
Mamy podstawową funkcję analizy leksykalnej (
ReadSymbol), która „podczepiona” pod string wejściowy podaje kolejne symbole z tego stringu. Ujmując to prościej, funkcja pobiera kolejne znaczki z wejściowego stringu i zwraca symbol wczytanego elementu (dodatkowo w zmiennej
Spelling jest treść tego symbolu). Tu warto zauważyć, że oprócz zestawu słów kluczowych, ta funkcja posiłkuje się tablicą znakową, w której również zdefiniowane są symbole (nie ma znaczenia, czy w wyrażeniu wystąpi wyraz „AND” czy znaczek & → jest to rozpoznany operator logiczny.
Wspomniana funkcja ma następującą postać:
Kod: Zaznacz cały
function TLogicExpressionForm.ReadSymbol : SymbolType ;
var
CharIndex : integer ;
LocalSymbol : SymbolType ;
Index : SymbolType ;
Ch : char ;
WorkSpelling : ObjectNameType ;
begin (* TLogicExpressionForm.ReadSymbol *)
Ch := NextChar ;
while ( Ch = Space ) and ( CharPosition <= CurrentLineSize ) do
Ch := NextChar ;
if Ch = chr ( 0 ) then
begin (* 1 *)
Spelling := '<EOLN>' ;
ReadSymbol := EoLnSy ;
exit ;
end (* 1 *) ;
if Letter ( Ch ) then
begin (* 1 *)
LocalSymbol := IdentSy ;
CharIndex := 1 ;
Spelling := Ch ;
WorkSpelling := UpCase ( Ch ) ;
Ch := NextChar ;
while AlfaChar ( Ch ) do
begin (* 2 *)
CharIndex := succ ( CharIndex ) ;
if CharIndex <= KeyLength then
begin (* 3 *)
Spelling := concat ( Spelling , Ch ) ;
WorkSpelling := concat ( WorkSpelling , UpCase ( Ch ) ) ;
end (* 3 *) ;
Ch := NextChar ;
end (* 2 *) ;
CharPosition := pred ( CharPosition ) ;
for Index := LogicAndOpSy to EndDictSy do
if WorkSpelling = Keywords [ Index ] then
LocalSymbol := Index ;
end (* 1 *)
else
if Ch < #127 then
begin (* 1 *)
Spelling := Ch ;
LocalSymbol := CharSymbol [ Ch ] ;
end (* 1 *)
else
begin (* 1 *)
LocalSymbol := NoSy ;
end (* 1 *);
ReadSymbol := LocalSymbol ;
end (* TLogicExpressionForm.ReadSymbol *) ;
Teraz sama analiza wyrażenia, więc wróćmy do definicji
<czynnik> ::= <identyfikator> | <stała logiczna> | ( wyrażenie proste> )
mamy dokładnie to odzwierciedlone w algorytmie (rozróżnienie na stałą logiczną, zmienną logiczną lub wyrażenie proste ujęte w nawiasy):
Kod: Zaznacz cały
procedure MultiplicativeExpression ;
var
TermEntry : ObjectRecordPtr ;
begin (* MultiplicativeExpression *)
if ( Symbol = TrueSy ) or ( Symbol = FalseSy ) then
IPNLoadLogicConst ( Symbol = TrueSy )
else
if Symbol = IdentSy then
begin (* 1 *)
TermEntry := FindObject ( Spelling ) ;
if TermEntry <> nil then
IPNVariable ( UpperCase ( Spelling ) )
else
Error ( UndefinedElementErrorCode ) ;
end (* 1 *)
else
if Symbol = LeftParSy then
begin (* 1 *)
Symbol := ReadSymbol ;
SimpleExpression ;
if Symbol <> RightParSy then
Error ( ExpectedRightParErrorCode ) ;
end (* 1 *)
else
Error ( UndefinedElementErrorCode ) ;
Symbol := ReadSymbol ;
end (* MultiplicativeExpression *) ;
kolejny element definicji wyrażenia:
<składnik> ::= <czynnik> | <czynnik> <operator multiplikatywny> <czynnik>
ma swoje odzwierciedlenie w algorytmie (funkcja MultiplicativeExpression obrabia <czynnik>):
Kod: Zaznacz cały
procedure AdditiveExpression ;
var
MultOperator : SymbolType ;
begin (* AdditiveExpression *)
MultiplicativeExpression ;
while ( Symbol = LogicAndOpSy ) do
begin (* 1 *)
MultOperator := Symbol ;
Symbol := ReadSymbol ;
MultiplicativeExpression ;
IPNAddOperator ( MultOperator ) ;
end (* 1 *) ;
end (* AdditiveExpression *) ;
Kolejny „poziom” wyrażenia odpowiada definicji w notacji BNF:
<wyrażenie proste> ::= <operator jednoargumentowy> <składnik> | <wyrażenie addytywne>
Funkcja AdditiveExpression obrabia <składnik>.
Kod: Zaznacz cały
procedure SimpleExpression ;
var
AddOperator : SymbolType ;
LogicNot : boolean ;
begin (* SimpleExpression *)
LogicNot := False ;
if Symbol = LogicNotOpSy then
begin (* 1 *)
LogicNot := True ;
Symbol := ReadSymbol ;
end (* 1 *) ;
AdditiveExpression ;
if LogicNot then
IPNAddOperator ( LogicNotOpSy ) ;
while ( Symbol = LogicOrOpSy ) or ( Symbol = LogicExOrOpSy ) do
begin (* 1 *)
AddOperator := Symbol ;
Symbol := ReadSymbol ;
AdditiveExpression ;
IPNAddOperator ( AddOperator ) ;
end (* 1 *) ;
end (* SimpleExpression *) ;
A analiza całego wyrażenia to przede wszystkim analiza wyrażenia prostego (dalsza część to „odwrócenie” listy liniowej notacji odwrotnej polskiej, gdyż ta w zastosowanym rozwiązaniu nie tworzy kolejki typu FIFO).
Kod: Zaznacz cały
begin (* TLogicExpressionForm.GetLogicExpression *)
ExpressionEntry := nil ;
SimpleExpression ;
TmpExpression := ExpressionEntry ;
ExpressionEntry := nil ;
while TmpExpression <> nil do
begin (* 1 *)
Element := TmpExpression ;
TmpExpression := TmpExpression ^ . FwdLink ;
Element ^ . FwdLink := ExpressionEntry ;
ExpressionEntry := Element ;
end (* 1 *) ;
GetLogicExpression := ExpressionEntry ;
end (* TLogicExpressionForm.GetLogicExpression *) ;
Tu nie trzeba nic kombinować i „naginać” do rzeczywistości. Jak na początku właściwie podejść do tematu, całość niejako sama się rozwiąże. Prawda, że proste?