[Question]
  [
Consider a grammar over the alphabet **{**`0`**,** `1`**,** `?`**,** `:`**}** defined by the [production rule](https://en.wikipedia.org/wiki/Production_(computer_science)#Grammar_generation)
> 
> s → `0` ┃ `1` ┃ `0` `?` s `:` s ┃ `1` `?` s `:` s
> 
> 
> 
Given a string generated from *s*, parse it as an expression where `?:` is right-associative (for example, `a?B?X:Y:c?d:e?f:g` means `a?(B?X:Y):(c?d:(e?f:g))`) and evaluate it with the following semantics:
```
eval(0) = 0
eval(1) = 1
eval(0?a:b) = eval(b)
eval(1?a:b) = eval(a)
```
If the result is **0**, output some fixed value; if the output is **1**, output a different fixed value. Specify your chosen output values (e.g. `0`/`1`, or `False`/`True`) in your answer.
## Test cases
```
0 -> 0
1 -> 1
0?0:1 -> 1
0?1:0 -> 0
1?0:1 -> 0
1?1:0 -> 1
0?1?0:1:1 -> 1
1?0?1:1:1 -> 1
1?0:1?0:1?1:1 -> 0
1?1?1:0?1?0:0:0:0 -> 1
1?0:1?0?1:1?1:0:1?1?1:1:1?0:1 -> 0
1?1?1:0?0?1:1:0?1:0:1?1?0?0:0:1?1:0:0?1?0:1:1?0:1 -> 1
0?0?1?0?0:1:0?0:0:0?0?1:1:1?0:1:0?0?0?1:0:0?1:1:1?1?0:1:1 -> 0
```
## Rules
* You may not use language built-ins that interpret strings as code in some [programming language](http://meta.codegolf.stackexchange.com/a/2073/3852) and run it (such as JavaScript/Perl/Ruby/Python’s `eval`).
* That said, your code doesn’t *actually* have to parse and then evaluate the input string. You can take any approach the achieves equivalent results and doesn’t violate the previous rule.
* Your program will be checked against `perl -le 'print eval<>'`.
* The shortest code (in bytes) wins.
  
[Answer]
## [Retina](https://github.com/m-ender/retina/), 23 bytes
```
r-1=+`0\?.:|1\?(.):.
$1
```
[Try it online!](http://retina.tryitonline.net/#code=JShHYApyLTE9K2AwXD8uOnwxXD8oLik6LgokMQ&input=MAoxCjA_MDoxCjA_MTowCjE_MDoxCjE_MTowCjE_MDoxPzA6MT8xOjEKMT8xPzE6MD8xPzA6MDowOjAKMT8wOjE_MD8xOjE_MTowOjE_MT8xOjE6MT8wOjEKMT8xPzE6MD8wPzE6MTowPzE6MDoxPzE_MD8wOjA6MT8xOjA6MD8xPzA6MToxPzA6MQowPzA_MT8wPzA6MTowPzA6MDowPzA_MToxOjE_MDoxOjA_MD8wPzE6MDowPzE6MToxPzE_MDoxOjE) (The first line enables a linefeed-separated test suite.)
### Explanation
It's fairly simple actually. The input is reduced to the result by repeatedly (`+`) evaluating ternaries that contain only literals. To make sure this is done right-associatively, we look for matches from right to left (`r`) and replace only the last match we find (`-1=`).
The regex itself either matches `0\?.:` and removes it (leaving only the stuff after `:`) or `1\?.:.` and replaces it with the value after the `?`.
[Answer]
# Haskell, ~~106 101 100 90~~ 83 bytes
This heavily relies on pattern Haskell's pattern matching capabilities. First of all, we reverse the string such that we can just seach for the first occurence of `b:a?x` (which would normally read as `x?a:b`) and replace it with it's value. This automatically provides the *right associativity*. Here we make use of `x:xs` pattern. This is what the function `f` is doing. Then we basically apply `f` to it's output over and over again, until we have a single number (0 or 1) left.
Thanks @Lynn for 12 bytes!
```
f(b:':':a:'?':x:l)|x>'0'=a:l|1>0=b:l
f(x:l)=x:f l
f x=x
until((<2).length)f.reverse
```
[Answer]
## Brainfuck, ~~82~~ ~~64~~ 63 bytes
```
+
[
  ,>>,>
  +++++++[<---<<-[------>>]<-]
  <<
  [
    ->[<++>[+]]
  ]
  +>[>>]
  <<<-
]
<.
```
The output is `\xff` for `0` and `\x00` for `1`. The brainfuck implementation must allow going to the left of the starting cell.
This uses essentially the same approach as xsot's Python [answer](https://codegolf.stackexchange.com/a/89882/2537), but the branching is probably harder to follow compared with my initial 82-byte submission:
```
-
[
  +
  [
    ->,,>+++++++[<--------->-]
    <[<++>[+]]
    <
  ]
  ,->,>+++++++[<[-------<]>>-->-]
  <[<]
  <
]
>>.
```
(For this solution, the output is `\xfe` for `0` and `\xff` for `1`, and wider compatibility is achieved when the input ends with a newline.)
If you can't be bothered to analyse xsot's solution, the idea is this: Proceed from left to right. If you see `1?` then greedily discard it. If you see `0?` then discard everything between that and the corresponding `:`. When `?` does not appear as the second character, stop looping and print the first character of the remaining string.
So, the 82-byte solution actually mirrors that scheme pretty closely. The inner loop handles `0?`, just like xsot's inner loop. Some care is taken in order to enter the main loop without checking any input characters; i.e., we want to check whether the second character is `?` just once at the end of the main loop, and not also at the beginning before entering the main loop.
The 63-byte solution essentially combines the inner and outer loops into one, which I suspected was possible given the similarity between those loops. The memory layout in the main loop could be described as:
```
[s] d c
```
where `[x]` means current cell -- the `s` starts as a dummy nonzero value that just indicates we are still looping, and is immediately overwritten with an input character (either `0` or `1`). The `d` cell holds the (negative) depth in case we are in the middle of a `0?`, otherwise `0`. The `c` is going to be either `?` or `:` or newline or EOF.
After updating `s` and `c`, we handle the `0?` case by updating `d` accordingly and adjusting the pointer, otherwise we use the current value of `c` as the value of `d` in the next iteration, or stop if we are done.
[Answer]
## Python 2, ~~76~~ ~~74~~ ~~73~~ 72 bytes
```
a=`id`
for c in input()[::-1]:a=(c+a,a[ord(c)*7%9]+a[4:])[a>'?']
print a
```
With input as string literal to avoid `raw_`.
The output is `0` or `1` followed by `<built-in function id>`.
[Answer]
## GolfScript, 21 bytes
```
2/-1%{)2%{0`=@@if}*}/
```
This outputs `0` or `1`. Input is assumed to have a single trailing newline. Using `~` (which evaluates strings) would save a byte:
```
2/-1%{)2%{~!@@if}*}/
```
This is based on <http://golf.shinh.org/reveal.rb?The+B+Programming+Language/tails_1462638030&gs> .
[Answer]
# Python 2, 89 bytes
```
s=input()
while'?'<=s[1:]:
 n=s<'1'
 while n:s=s[2:];n+=-(s[1]<'?')|1
 s=s[2:]
print s[0]
```
Input is taken as a string literal. 
[Answer]
## [Grime](https://github.com/iatorm/grime), ~~34~~ 31 bytes
```
E=d|d\?E.E
e`\1|\1\?_.E|\0\?E._
```
Prints `1` for truthy inputs and `0` for falsy ones.
[Try it online!](http://grime.tryitonline.net/#code=RT1kfGRcP0UuRQplYFwxfFwxXD9fLkV8XDBcP0UuXw&input=MT8xPzE6MD8xPzA6MDowOjA)
The last test case unfortunately runs out of memory on TIO.
## Explanation
The right-associativity essentially means that in `a?b:c`, `a` is always either `0` or `1`, never a longer expression.
I'll just recursively define a pattern that matches a truthy expression like that, and check the input against it.
It's also unnecessary to check that every `:` is really a `:`, if the `?`s are all checked: there is an equal number of `?`s and `:`s in the input, and if some `?` is incorrectly classified as a `:`, the corresponding `:` will fail to match, and Grime's matching engine will backtrack.
```
E=d|d\?E.E
E=                      Define nonterminal E (for "expression") as
  d|                     a digit, OR
    d                    a digit,
     \?                  a literal ?,
       E                 a match of E,
        .                any character (will match a :), and
         E               another match of E.
e`\1|\1\?_.E|\0\?E._
e`                      Match entire input against this pattern (truthy expression):
  \1|                    a literal 1, OR
     \1\?                a literal 1?,
         _               a recursive match of truthy expression,
          .              any character (will match a :), and
           E|            any expression, OR
             \0\?E._     the same, but with 0 in front, and _ and E swapped.
```
[Answer]
# Haskell, ~~79 71 70 62 60~~ 56 bytes
**Edit:** Thanks to @Zgarb for 3 bytes and to @nimi for 4 bytes!
```
e(x:'?':r)|a:_:s<-e r=last$e s:[a:tail(e s)|x>'0']
e x=x
```
This a recursive approach ~~that somewhat abuses the "some fixed value"-output rule~~. Edit: Getting rid of the tuples doesn't only save 8 bytes, it also yields a nicer output: `"0"` or `"1"`.
**Ungolfed version:**
```
eval (x:'?':r1) = if x=='1' then (a, r3) else (b, r3)
    where (a,':':r2) = eval r1
          (b, r3)    = eval r2
eval (x:r) = (x,r)
```
**How does it work?**  
The `eval` function traverses the implicit tree of the expressions
```
eval 1?0?0:1:0?1:0 -> eval 1?          :
                             eval 0?0:1 eval 0?1:0
```
and returns a tuple of the form `(result, rest)`.  
The first pattern `(x:'?':r1)` matches `x` to `'1'` and `r1` to `"0?0:1:0?1:0"`. Recursively applying `eval` to `r1` evaluates the sub-expression `0?0:1` and returns `(0,":0?1:0")`. Matching this to the pattern `(a,':':r2)` yields `a=0` and `r2=0?1:0`. This sub-formula is also recursively evaluated so that `b='0'` and `r3=""`. Check if `x` is `'1'` or `'0'` and return either `(a, r3)` or `(b, r3)`.
[Answer]
## JavaScript (ES6), 53 bytes
```
f=s=>s[1]?f(s.replace(/0\?.:|1\?(.):.(?!\?)/,"$1")):s
```
Returns `0` or `1` for valid input; hangs for invalid input. Explanation: because reversing a string is awkward in JavaScript, my first 71-byte attempt worked by using a negative lookahead for a `?` which would otherwise disturb the associativity:
```
f=s=>s[1]?f(s.replace(/(.)\?(.):(.)(?!\?)/,(_,a,b,c)=>+a?b:c)):s
```
Since this was somewhat long I wondered whether I could improve matters by incorporating the decision making into the regexp. As it turned out, it wasn't an immediate success, as it also took 71 bytes:
```
f=s=>s[1]?f(s.replace(/0\?.:(.)(?!\?)|1\?(.):.(?!\?)/,"$1$2")):s
```
Then it occurred to me that `0?0:` and `0?1:` are always no-ops, without concern for associativity. This saved me almost 25%.
[Answer]
## Perl, 32 + 1 (`-p` flag) = 33 bytes
*Full credit to [@Mitch Swartch](https://codegolf.stackexchange.com/users/2537/mitch-schwartz), as his solution was 14 bytes shorter than mine!*  
*Thanks also to [@Neil](https://codegolf.stackexchange.com/users/17602/neil) who suggested a solution 1 byte longer than Mitch.*
```
s/.*\K(0\?..|1\?(.)..)/\2/&&redo
```
Needs `-p` flag, as well as `-M5.010` or `-E` to run. For instance :
```
perl -pE 's/.*\K(0\?..|1\?(.)..)/\2/&&redo' <<< "0
0?0:1
0?1?0:1:1
1?0:1?0?1:1?1:0:1?1?1:1:1?0:1
0?0?1?0?0:1:0?0:0:0?0?1:1:1?0:1:0?0?0?1:0:0?1:1:1?1?0:1:1"
```
**Explanations** : It basically reduces the blocks of `a?b:c` (starting from the end to be sure no `?` follows) into `b` or `c` depending on the truthness of `a`, over and over until the string only contains `1` or `0`.
[Answer]
## Python 3, ~~93~~ 69 bytes
```
def f(s):z=s.pop;r=z(0);return s and':'<z(0)and(f(s),f(s))[r<'1']or r
```
Input is the string as a list of characters, output is either `"0"` or `"1"`
```
>>>f(list("0?0:1"))
<<<"1"
```
---
Ungolfed version:
```
def parse(s):
    predicate = s.pop(0)
    if s and s.pop(0) == '?':
        left, right = parse(s), parse(s)
        if predicate == '0':
            return right
        return left
    return predicate
```
---
Another try, but with considerably more bytes:
```
i=input()[::-1]
a=[i[0]]
for o,z in zip(i[1::2],i[2::2]):a+=[z]if o<'?' else[[a.pop(),a.pop()][z>'0']]
print(a[0])
```
[Answer]
# SED, 75 74 68 (40 + 1 for -r) 41
```
:
s,(.*)1\?(.):.,\1\2,
s,(.*)0\?.:,\1,
t
```
[Answer]
# Bash + GNU utilities, 42
```
rev|sed -r ':
s/(.):.\?0|.:(.)\?1/\1\2/
t'
```
Similar idea to most of the other pattern-matching answers.
[Ideone](https://ideone.com/5CMYYQ).
]