WebHU - Programozási kérdések és válaszok

A szükségtelen legkülső zárójelek letiltása a BNFC-nyelvtanban

Ez a ennek folytatása. a> kérdés, amit korábban feltettem egy BNFC-grammatikáról a propozíciós logikához. A definíció szerint zárójelekkel dolgoztam, de most szeretném kiterjeszteni a nyelvtant zárójel nélkülire, de egy fogással: felesleges külső zárójelek nem megengedettek.

Például a a atommondatot engedélyezni kell, de a (a)-t nem szabad felismerni. A (a => b) & c mondatot is engedélyezni kell, de a ((a => b) & c) nem, és így tovább. Az utolsó példa rávilágít a zárójelek szükségességére. Az elsőbbségi szintek a következők

  1. egyenértékűség <=> és implikáció =>,
  2. konjunkció & és diszjunkció |
  3. tagadás - és
  4. atomok.

Minél magasabb a szint, annál korábban kerül elemzésre.

A nyelvtant a szükségtelen zárójelekkel dolgoztam fel úgy, hogy rekurzióval prioritási szinteket állítottam be a különböző operátorokhoz:

IFF     .   L     ::=   L   "<=>" L1  ;
IF      .   L     ::=   L   "=>"  L1  ;
AND     .   L1    ::=   L1  "&"   L2  ;
OR      .   L1    ::=   L1  "|"   L2  ;
NOT     .   L2    ::=       "-"   L3  ;
NOT2    .   L2    ::=       "-"   L2  ;
P       .   L3    ::=   Ident         ;

_       .   L     ::=   L1            ;
_       .   L1    ::=   L2            ;
_       .   L2    ::=   L3            ;
_       .   L3    ::=   "(" L ")"     ;

Most az a kérdés, hogyan nem engedhetem be a külső zárójeleket, aminek a megengedését az utolsó L3 ::= "(" L ")"; szabály okozza? Feltétlenül szükséges a zárójelek egy kifejezésen belüli engedélyezéséhez, de az éleken is engedélyezi. Azt hiszem, szükségem van valami extra szabályra a kétértelműség megszüntetésére, de milyen lehet az?

Ez a nyelvtan körülbelül 6 redukciós/kicsinyítési konfliktust is eredményez, de ezek nem elkerülhetetlenek a rekurzív definíciókban?

parsing grammar context-free-grammar bnfc
15.04.2020

  • Megpróbálhatja megkettőzni egyes produkcióit, megtiltva, hogy egy produkció közvetlenül L-ről L3-ra kerüljön, ha eltérő L' legyen a L ::= L' "<=>" L1 és L ::= L' "=>" L1 produkciókban. Ebben az esetben a produkciók L' duplikátumai konvertálhatók le L3-re, de maga a L nem. Tehát a ' rész azt jelzi, hogy a gyártás tényleges bővítésben vett részt, nem csak az elsőbbség kedvéért történt átalakításban. A ' duplikátumok körül zárójelek lehetnek, de a nem ' másolatok nem. 15.04.2020
  • @Welbog Tehát alapvetően ez a 4 produkció lenne az első szintre: L ::= L' "<=>" L1, L ::= L' "=>" L1, L' ::= L' "<=>" L1 és L' ::= L' "=>" L1. Ezután az L3-el zárójelbe teszem a L' verziókat, így: _. L3 ::= "(" L' ")";. 15.04.2020

Válaszok:


1

Ezt úgy teheti meg, hogy egyszerűen kitiltja a zárójeles űrlapot a felső szintről. Ehhez az elsőbbségi hierarchiát más módon kell megírni, hogy a korlátozást a hierarchián keresztül terjeszthessük. A következőkben a r utótag azt jelzi, hogy a produkció nem lehet zárójeles forma.

A redukálás/csökkentés konfliktusokat az egyik NOT produkció kiiktatásával is javítottam. Lásd alább.

(Remélem jól értelmeztem a BNFC-t. Ezt bölényben írtam, és megpróbáltam utána konvertálni a szintaxist.)

_       .   S     ::=   L0r             ;

IFF     .   L0r   ::=   L0 "<=>" L1     ;
IF      .   L0r   ::=   L0 "=>"  L1     ;

AND     .   L1r   ::=   L1 "&"   L2     ;
OR      .   L1r   ::=   L1 "|"   L2     ;

NOT     .   L2r   ::=       "-"   L2    ;
ID      .   L2r   ::=   Ident           ;                                            

PAREN   .   L3    ::=   "(" L0 ")"      ;

_       .   L0r   ::=   L1r             ;
_       .   L1r   ::=   L2r             ;

_       .   L0    ::=   L0r             ;
_       .   L1    ::=   L1r             ;
_       .   L2    ::=   L2r             ;

_       .   L0    ::=   L3              ;
_       .   L1    ::=   L3              ;
_       .   L2    ::=   L3              ;

(Szerkesztés: Módosítottam a IFF, IF, AND és OR szabályokat azáltal, hogy eltávolítottam a korlátozást (r) az első argumentumokból. Ez lehetővé teszi, hogy a szabályok illeszkedjenek a zárójellel kezdődő kifejezésekhez anélkül, hogy megegyeznének a PAREN szintaxissal .)

Ha a redundáns belső zárójeleket (például ((a & b))) is szeretné letiltani, módosíthatja a PAREN szabályt a következőre:

PAREN   .   L3    ::=   "(" L0r ")"     ;

ami szükségtelenné tenné a L0 szabályt.

Az @IraBaxter válaszában található egy változatos megközelítés, amely kevesebb egységgyártást használ. ://stackoverflow.com/questions/36001979/grammar-for-expressions-which-disallows-outer-parenthes">A külső zárójeleket nem engedélyező kifejezések nyelvtana.

Oldaljegyzet:

Ez a nyelvtan körülbelül 6 redukciós/kicsinyítési konfliktust is eredményez, de ezek nem elkerülhetetlenek a rekurzív definíciókban?

Nem, a rekurzív nyelvtan lehet és kell is, hogy egyértelmű legyen. A konfliktusok csökkentése/csökkentése nem elkerülhetetlen, és szinte mindig nyelvtani problémákat jelez. Ebben az esetben ezek az unáris NEM operátor redundáns produkcióinak eredményei. Ha két különböző nem-terminál van, amelyek képesek elfogadni a "-" L3 értéket, az nyilvánvalóan kétértelműséghez vezet, és a kétértelműségek mindig elemzési konfliktusokat okoznak.

15.04.2020
  • Ez ad egy ötletet, hogyan kell ezt megtenni, de figyelmen kívül hagytál néhány, a BNFC által támasztott szabályt, így ez nem lesz teljesen lefordítva. A r utótagokat számokká kell alakítani, és a | szimbólumot nem ismeri fel a rendszer, mint a BNF sok más változatában. Az utolsó szabályoknak a saját sorukban kell lenniük. 15.04.2020
  • @sesodesa: Bocsi, nem használok BNFC-t. Van valami referencia dokumentumod? (Alternatív megoldásként beletehetem a bölény verziót is, ami lefordítja és lefut :-) ) 15.04.2020
  • @Sesodesa: OK, javítottam a | használatát. Feltételezve, hogy ez az a BNFC, amelyről beszél, nem látok semmit, ami problémássá tenné a L1r használatát. 15.04.2020
  • Nos, a szerkesztetlen válasz egyszerűen nem jött össze nekem, mivelbnfc panaszkodott ezekről a konkrét szabályokról. A probléma az, hogy látszólag a kényszerített szabályoknak ugyanazzal az alapazonosítóval kell rendelkezniük (betűkből álló előtag), és a különböző kényszerítési szinteket postfix számok választják el. Ennek magyarázata itt. 15.04.2020
  • @SeSodesa: ok, elolvasom és megpróbálom javítani. De az ötlet világos, nem? 15.04.2020
  • Ezen még gondolkodnom kell (a produkciók alapján készítsek néhány levezetést), de azt hiszem, a lényeget értem. Ezzel a konstrukcióval nem tudunk olyan karakterláncot származtatni, amely ( karakterrel kezdődik. Egyébként szerintem a S kezdőszimbólumhoz is kell egy címke, például Start . S ::= L;. Úgy tűnik, a BNFC is panaszkodik, ha nincs legalább egy szabály, amelynek végén nincs számjegy, ez a L típusú produkciók úgynevezett alapesete. 15.04.2020
  • A mondatok azért nem kezdődhetnek (-el, mert a L1 és L2 változókat az ezeket használó produkciók végére helyezted. 15.04.2020
  • @SeSodesa: Igen, igazad van, és ez azt jelenti, hogy rosszul csináltam. Egy másik problémát oldottam meg: hogyan lehet tiltani a zárójellel kezdődő kifejezéseket. (Ez elég gyakran előjön, mert azokban a nyelvekben, ahol a kifejezések utasítások, és az utasításokat nem kell pontosvesszővel elválasztani, kerülni kell a zárójellel kezdődő utasításkifejezéseket, hogy elkerüljük a függvényhívások kétértelműségét). De a te eseted más. Kicsit eljátszottam a BNFC-vel, és van valami, amire nem panaszkodik, úgyhogy ezzel szerkesztem a választ. 16.04.2020
    • Új anyagok
    A rádiógomb ellenőrzött eseményének használata a jQueryben
    Ebben a cikkben látni fogjuk, hogyan kell dolgozni a jquery választógombbal ellenőrzött eseményeivel. A választógombok HTML gombok, amelyek segítenek kiválasztani egyetlen értéket egy csoportból...
    Körkörös függőségek megoldása terraformban adatforrásokkal – lépésről lépésre
    Mi az a körkörös függőségek Dolgozzunk egy egyszerű eseten, amikor az SQS-sor és az S3-vödör közötti körkörös függőség problémája van egy egymástól függő címkeérték miatt. provider..
    Miért érdemes elkezdeni a kódolást 2023-ban?
    01100011 01101111 01100100 01100101 — beep boop beep boop Világunk folyamatosan fejlődik a technológia körül, és naponta fejlesztenek új technológiákat a valós problémák megoldására. Amint..
    🎙 Random Noise #2  – Örökbefogadás és hit
    az analitika íratlan világának gondozása Szeretné, hogy ezek a frissítések a postaládájába kerüljenek? Iratkozzon fel itt . "Ha önvezető autókat gyártanak, akkor mi miért ne..
    A legrosszabb politika és prediktív modellek májátültetésre jelöltek számára az Egyesült Államokban
    A máj (vagy óangolul lifer) az emberi test legnehezebb belső szervére utal, amely csendesen működik a nap 24 órájában. Mit csinál a máj? 500 feladatot hajt végre a szervezet egészségének..
    5 webhely, amely 2022-ben fejleszti front-end fejlesztői készségeit
    Frontendmentor.io A tényleges projektek létrehozásával a Frontendmentor.io segítséget nyújt a front-end kódolási képességeinek fejlesztésében. A kódolást azután kezdheti meg, hogy..
    Mikor kell használni a Type-t az interfészhez képest a TypeScriptben?
    A TypeScript a JavaScript gépelt szuperkészlete, amely statikus gépelést ad a nyelvhez. Ez megkönnyíti a robusztus és karbantartható kód írását azáltal, hogy a hibákat a fordítási időben..