lib/ParserGenerator/PHP/ParserGenerator/Data.php
function FindFirstSets()
    {
        for ($i = 0; $i < $this->nsymbol; $i++) {
            $this->symbols[$i]->lambda = false;
        }
        for($i = $this->nterminal; $i < $this->nsymbol; $i++) {
            $this->symbols[$i]->firstset = array();
        }

        /* First compute all lambdas */
        do{
            $progress = 0;
            for ($rp = $this->rule; $rp; $rp = $rp->next) {
                if ($rp->lhs->lambda) {
                    continue;
                }
                for ($i = 0; $i < $rp->nrhs; $i++) {
                    $sp = $rp->rhs[$i];
                    if ($sp->type != PHP_ParserGenerator_Symbol::TERMINAL || $sp->lambda === false) {
                        break;
                    }
                }
                if ($i === $rp->nrhs) {
                    $rp->lhs->lambda = true;
                    $progress = 1;
                }
            }
        } while ($progress);

        /* Now compute all first sets */
        do {
            $progress = 0;
            for ($rp = $this->rule; $rp; $rp = $rp->next) {
                $s1 = $rp->lhs;
                for ($i = 0; $i < $rp->nrhs; $i++) {
                    $s2 = $rp->rhs[$i];
                    if ($s2->type == PHP_ParserGenerator_Symbol::TERMINAL) {
                        //progress += SetAdd(s1->firstset,s2->index);
                        $progress += isset($s1->firstset[$s2->index]) ? 0 : 1;
                        $s1->firstset[$s2->index] = 1;
                        break;
                    } elseif ($s2->type == PHP_ParserGenerator_Symbol::MULTITERMINAL) {
                        for ($j = 0; $j < $s2->nsubsym; $j++) {
                            //progress += SetAdd(s1->firstset,s2->subsym[j]->index);
                            $progress += isset($s1->firstset[$s2->subsym[$j]->index]) ? 0 : 1;
                            $s1->firstset[$s2->subsym[$j]->index] = 1;
                        }
                        break;
                    } elseif ($s1 === $s2) {
                        if ($s1->lambda === false) {
                            break;
                        }
                    } else {
                        //progress += SetUnion(s1->firstset,s2->firstset);
                        $test = array_diff_key($s2->firstset, $s1->firstset);
                        if (count($test)) {
                            $progress++;
                            $s1->firstset += $test;
                        }
                        if ($s2->lambda === false) {
                            break;
                        }
                    }
                }
            }
        } while ($progress);
    }
function FindFirstSets()
    {
        for ($i = 0; $i < $this->nsymbol; $i++) {
            $this->symbols[$i]->lambda = false;
        }
        for($i = $this->nterminal; $i < $this->nsymbol; $i++) {
            $this->symbols[$i]->firstset = array();
        }

        /* First compute all lambdas */
        do{
            $progress = 0;
            for ($rp = $this->rule; $rp; $rp = $rp->next) {
                if ($rp->lhs->lambda) {
                    continue;
                }
                for ($i = 0; $i < $rp->nrhs; $i++) {
                    $sp = $rp->rhs[$i];
                    if ($sp->type != PHP_ParserGenerator_Symbol::TERMINAL || $sp->lambda === false) {
                        break;
                    }
                }
                if ($i === $rp->nrhs) {
                    $rp->lhs->lambda = true;
                    $progress = 1;
                }
            }
        } while ($progress);

        /* Now compute all first sets */
        do {
            $progress = 0;
            for ($rp = $this->rule; $rp; $rp = $rp->next) {
                $s1 = $rp->lhs;
                for ($i = 0; $i < $rp->nrhs; $i++) {
                    $s2 = $rp->rhs[$i];
                    if ($s2->type == PHP_ParserGenerator_Symbol::TERMINAL) {
                        //progress += SetAdd(s1->firstset,s2->index);
                        $progress += isset($s1->firstset[$s2->index]) ? 0 : 1;
                        $s1->firstset[$s2->index] = 1;
                        break;
                    } elseif ($s2->type == PHP_ParserGenerator_Symbol::MULTITERMINAL) {
                        for ($j = 0; $j < $s2->nsubsym; $j++) {
                            //progress += SetAdd(s1->firstset,s2->subsym[j]->index);
                            $progress += isset($s1->firstset[$s2->subsym[$j]->index]) ? 0 : 1;
                            $s1->firstset[$s2->subsym[$j]->index] = 1;
                        }
                        break;
                    } elseif ($s1 === $s2) {
                        if ($s1->lambda === false) {
                            break;
                        }
                    } else {
                        //progress += SetUnion(s1->firstset,s2->firstset);
                        $test = array_diff_key($s2->firstset, $s1->firstset);
                        if (count($test)) {
                            $progress++;
                            $s1->firstset += $test;
                        }
                        if ($s2->lambda === false) {
                            break;
                        }
                    }
                }
            }
        } while ($progress);
    }
function FindFirstSets ( ) { for ( $ i = 0 ; $ i < $ this -> nsymbol ; $ i ++ ) { $ this -> symbols [ $ i ] -> lambda = false ; } for ( $ i = $ this -> nterminal ; $ i < $ this -> nsymbol ; $ i ++ ) { $ this -> symbols [ $ i ] -> firstset = array ( ) ; } /* First compute all lambdas */ do { $ progress = 0 ; for ( $ rp = $ this -> rule ; $ rp ; $ rp = $ rp -> next ) { if ( $ rp -> lhs -> lambda ) { continue ; } for ( $ i = 0 ; $ i < $ rp -> nrhs ; $ i ++ ) { $ sp = $ rp -> rhs [ $ i ] ; if ( $ sp -> type != PHP_ParserGenerator_Symbol :: TERMINAL || $ sp -> lambda === false ) { break ; } } if ( $ i === $ rp -> nrhs ) { $ rp -> lhs -> lambda = true ; $ progress = 1 ; } } } while ( $ progress ) ; /* Now compute all first sets */ do { $ progress = 0 ; for ( $ rp = $ this -> rule ; $ rp ; $ rp = $ rp -> next ) { $ s1 = $ rp -> lhs ; for ( $ i = 0 ; $ i < $ rp -> nrhs ; $ i ++ ) { $ s2 = $ rp -> rhs [ $ i ] ; if ( $ s2 -> type == PHP_ParserGenerator_Symbol :: TERMINAL ) { //progress += SetAdd(s1->firstset,s2->index); $ progress += isset ( $ s1 -> firstset [ $ s2 -> index ] ) ? 0 : 1 ; $ s1 -> firstset [ $ s2 -> index ] = 1 ; break ; } elseif ( $ s2 -> type == PHP_ParserGenerator_Symbol :: MULTITERMINAL ) { for ( $ j = 0 ; $ j < $ s2 -> nsubsym ; $ j ++ ) { //progress += SetAdd(s1->firstset,s2->subsym[j]->index); $ progress += isset ( $ s1 -> firstset [ $ s2 -> subsym [ $ j ] -> index ] ) ? 0 : 1 ; $ s1 -> firstset [ $ s2 -> subsym [ $ j ] -> index ] = 1 ; } break ; } elseif ( $ s1 === $ s2 ) { if ( $ s1 -> lambda === false ) { break ; } } else { //progress += SetUnion(s1->firstset,s2->firstset); $ test = array_diff_key ( $ s2 -> firstset , $ s1 -> firstset ) ; if ( count ( $ test ) ) { $ progress ++ ; $ s1 -> firstset += $ test ; } if ( $ s2 -> lambda === false ) { break ; } } } } } while ( $ progress ) ; }
Find all nonterminals which will generate the empty string.
Then go back and compute the first sets of every nonterminal.
The first set is the set of all terminal symbols which can begin
a string generated by that nonterminal.
Find all nonterminals which will generate the empty string . Then go back and compute the first sets of every nonterminal . The first set is the set of all terminal symbols which can begin a string generated by that nonterminal .