Lausekepuu on puu, jota käytetään edustamaan erilaisia lausekkeita. Puutietorakennetta käytetään esittämään lausekkeita. Tässä puussa sisäinen solmu ilmaisee aina operaattoreita.
- Lehden solmut osoittavat aina operandeja.
- Toiminnot suoritetaan aina näille operandeille.
- Puun syvyydessä oleva käyttäjä on aina korkeimmalla prioriteetilla.
- Käyttäjä, joka ei ole paljon puun syvyydessä, on aina alimmalla prioriteetilla verrattuna syvyydessä makaaviin käyttäjiin.
- Operandi esiintyy aina puun syvyydessä; siksi sitä pidetään korkein prioriteetti kaikkien toimijoiden kesken.
- Lyhyesti sanottuna voimme tiivistää sen, koska puun syvyydessä oleva arvo on korkein prioriteetti verrattuna muihin puun yläosassa oleviin operaattoreihin.
- Näiden ilmaisupuiden pääasiallinen käyttötarkoitus on, että se on tottunut arvioida, analysoida ja muuttaa erilaisia ilmaisuja.
- Sitä käytetään myös lausekkeen kunkin operaattorin assosiatiivisuuden selvittämiseen.
- Esimerkiksi +-operaattori on vasen assosiatiivinen ja / on oikea-assosiatiivinen.
- Tämän assosiatiivisuuden dilemma on selvitetty käyttämällä lausekepuita.
- Nämä lausekepuut muodostetaan käyttämällä yhteydetöntä kielioppia.
- Olemme yhdistäneet säännön yhteydettömiin kielioppiin jokaisen kielioppituotannon eteen.
- Näitä sääntöjä kutsutaan myös semanttisiksi säännöiksi, ja näiden semanttisten sääntöjen avulla voimme helposti rakentaa lausekepuut.
- Se on yksi kääntäjien suunnittelun tärkeimmistä osista ja kuuluu semanttisen analyysin vaiheeseen.
- Tässä semanttisessa analyysissä käytämme syntaksiohjattuja käännöksiä ja tuotoksen muodossa tuotamme annotoidun jäsennyspuun.
- Annotoitu jäsennyspuu ei ole muuta kuin yksinkertainen jäsennys, joka liittyy type-attribuuttiin ja jokaiseen tuotantosääntöön.
- Lausekepuiden käytön päätavoite on tehdä monimutkaisia lausekkeita ja niitä voidaan helposti arvioida näiden lausekepuiden avulla.
- Se on muuttumaton, ja kun olemme luoneet lausekepuun, emme voi muuttaa sitä tai muokata sitä enempää.
- Jos haluat tehdä lisää muutoksia, uusi lausekepuu on rakennettava kokonaan.
- Sitä käytetään myös postfix-, etuliite- ja infix-lausekkeen arvioinnin ratkaisemiseen.
Ilmaisupuilla on erittäin tärkeä rooli sen edustamisessa kielitasolla datan muodossa oleva koodi, joka on pääasiassa tallennettu puumaiseen rakenteeseen. Sitä käytetään myös muistikuvauksessa lambda ilmaisu. Puutietorakenteen avulla voimme ilmaista lambda-lausekkeen läpinäkyvämmin ja selkeämmin. Se luodaan ensin muuttamaan koodisegmentti datasegmentiksi, jotta lauseke voidaan helposti arvioida.
Lausekepuu on binääripuu, jossa jokainen ulkoinen tai lehtisolmu vastaa operandia ja jokainen sisäinen tai emosolmu vastaa operaattoreita, joten esimerkiksi lausekepuu 7 + ((1+8)*3) olisi:
Olkoon S lausekepuu
Jos S ei ole nolla, niin
Jos S.arvo on operandi, niin
Palauta S.-arvo
x = ratkaise (S.vasen)
y = ratkaise (S.oikea)
Palautuslaskenta(x, y, S.arvo)
Tässä yllä olevassa esimerkissä lausekepuussa käytettiin yhteydetöntä kielioppia.
Meillä on joitain tuotantoja, jotka liittyvät joihinkin tämän kieliopin tuotantosääntöihin, jotka tunnetaan pääasiassa nimellä semanttiset säännöt . Voimme määritellä tulosten tuottamisen vastaavista tuotantosäännöistä käyttämällä näitä semanttisia sääntöjä. Tässä on käytetty arvoparametria, joka laskee tuloksen ja palauttaa sen kieliopin alkusymboliin. S.left laskee solmun vasemman lapsen, ja vastaavasti solmun oikea lapsi voidaan laskea S.right-parametrilla.
Lausekepuun käyttö
- Lausekepuiden käytön päätavoite on tehdä monimutkaisia lausekkeita ja niitä voidaan helposti arvioida näiden lausekepuiden avulla.
- Sitä käytetään myös lausekkeen kunkin operaattorin assosiatiivisuuden selvittämiseen.
- Sitä käytetään myös postfix-, etuliite- ja infix-lausekkeen arvioinnin ratkaisemiseen.
Lausekepuun toteutus
Lausekepuun toteuttamiseksi ja sen ohjelman kirjoittamiseksi meidän on käytettävä pinotietorakennetta.
Koska tiedämme, että pino perustuu viimeinen ensin ulos LIFO -periaatteeseen, äskettäin pinoon työnnetty tietoelementti on ponnahtanut ulos aina tarvittaessa. Sen toteuttamiseen käytetään pinon kahta päätoimintoa, push ja pop. Push-operaatiolla työnnämme tietoelementin pinoon ja pop-operaatiolla poistamme tietoelementin pinosta.
Pinon päätoiminnot lausekepuun toteutuksessa:
Ensin skannataan annettu lauseke vasemmalta oikealle, sitten tarkistetaan yksitellen tunnistettu merkki,
- Jos skannattu merkki on operandi, käytämme push-toimintoa ja työnnämme sen pinoon.
- Jos skannattu merkki on operaattori, käytämme siihen pop-operaatiota poistaaksemme kaksi arvoa pinosta tehdäksemme niistä sen alatason, ja sen jälkeen työnnämme nykyisen pääsolmun takaisin pinoon.
Lausekepuun toteutus C-ohjelmointikielellä
// C program for expression tree implementation #include #include /* The below structure node is defined as a node of a binary tree consists of left child and the right child, along with the pointer next which points to the next node */ struct node { char info ; struct node* l ; struct node* r ; struct node* nxt ; }; struct node *head=NULL; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newnode(char data) { struct node* node = (struct node*) malloc ( sizeof ( struct node ) ) ; node->info = data ; node->l = NULL ; node->r = NULL ; node->nxt = NULL ; return ( node ) ; } void Inorder(struct node* node) { if ( node == NULL) return ; else { /* first recur on left child */ Inorder ( node->l ) ; /* then print the data of node */ printf ( '%c ' , node->info ) ; /* now recur on right child */ Inorder ( node->r ) ; } } void push ( struct node* x ) { if ( head == NULL ) head = x ; else { ( x )->nxt = head ; head = x ; } // struct node* temp ; // while ( temp != NULL ) // { // printf ( ' %c ' , temp->info ) ; // temp = temp->nxt ; // } } struct node* pop() { // Poping out the top most [pointed with head] element struct node* n = head ; head = head->nxt ; return n ; } int main() { char t[] = { 'X' , 'Y' , 'Z' , '*' , '+' , 'W' , '/' } ; int n = sizeof(t) / sizeof(t[0]) ; int i ; struct node *p , *q , *s ; for ( i = 0 ; i <n ; i++ ) { if read character is operator then popping two other elements from stack and making a binary tree ( t[i]="=" '+' || '-' '*' ' '^' s="newnode" t [ i ] p="pop()" q="pop()" s->l = q ; s->r = p; push(s); } else { s = newnode ( t [ i ] ) ; push ( s ) ; } } printf ( ' The Inorder Traversal of Expression Tree: ' ) ; Inorder ( s ) ; return 0 ; } </n> Yllä olevan ohjelman tulos on:
X + Y * Z / W
Lausekepuun toteutus C++-ohjelmointikielellä
// C++ program for expression tree #include using namespace std ; /* The below class node is defined as a node of a binary tree consists of left child and the right child, along with the pointer next which points to the next node */ class node { public: char info ; node* l ; node* r ; node* nxt = NULL ; node ( char c ) { this->info = c ; l = NULL ; r = NULL ; } node() { l = NULL ; r = NULL ; } friend class Stack ; friend class tree ; } ; class Stack { node* head = NULL ; public: void push ( node* ) ; node* pop() ; friend class tree ; } ; class tree { public: void inorder ( node* x ) { // cout<<'tree in inorder traversal is: '<l ) ; cout <info <r } void stack::push( node* x { if ( head="=" null we are inserting here nodes at the top of stack [following lifo principle] else x->nxt = head ; head = x ; } } node* Stack::pop() { // Poping out the top most [ pointed with head ] element node* p = head ; head = head->nxt ; return p ; } int main() { string str = 'XYZ*+W/' ; // If you wish take input from user: //cout << 'Insert Postorder Expression: ' <> s; Stack s ; tree t ; node *p, *q, *re; int n = str.length() ; for ( int i = 0 ; i <n ; i++ ) { if ( str[ i ]="=" '+' || '-' '*' ' '^') re="new" node( str[i] p="s.pop()" q="s.pop()" re->l = q ; re->r = p ; s.push(re) ; } else { re = new node( str[ i ] ) ; s.push(re) ; } } cout << ' The Inorder Traversal of Expression Tree: ' ; t.inorder(re) ; return 0 ; } </n></'tree> Yllä olevan ohjelman tulos on:
X + Y * Z / W
Lausekepuun toteutus Java-ohjelmointikielellä
// Java program for expression tree import java.util.* ; /* The below class node is defined as a node of a binary tree consists of left child and the right child, along with the pointer next which points to the next node */ class Node { char info ; Node l , r ; public Node(char data) { this.info = data ; l = null ; r = null ; } } public class Main { public static boolean isOperator ( char ch ) { if ( ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^' ) { return true ; } return false ; } public static Node Tree ( String postfix ) { Stack st = new Stack(); Node t1,t2,temp ; for ( int i = 0 ; i <p> <strong>The output of the above program is:</strong> </p> <pre> X + Y * Z / W </pre> <hr>